1. 
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 10023 Square Root
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=964&mosmsg=Submission+received+with+ID+7916991
*
* @author Barny Porcio
* @version 1.0, 04/22/2010
*
* Method : -
* Status : Accepted
* Runtime: 0.732
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

public class Main {

public static void main(String[] args) throws NumberFormatException, IOException {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for (int i = Integer.parseInt(br.readLine()); i > 0; --i){
br.readLine();
String val = br.readLine();
BigInteger bi = new BigInteger(val);
if (bi.equals(BigInteger.ZERO)){
System.out.println(0);
}
else{
//d ist eine grobe abschätzung der wurzel
BigInteger d;
if (val.length()%2 == 0)
d = BigInteger.TEN.pow((val.length()-2)/2).multiply(BigInteger.valueOf(6));
else
d = BigInteger.TEN.pow((val.length()-1)/2).multiply(BigInteger.valueOf(2));

//last speichert den letzten wert von d um zu sehen ab wann sich nichts mehr ändert
BigInteger last = BigInteger.ZERO;

// solange sich noch etwas ändert wird die babylonische methode erneut angewendet
for (int o = 0; true; ++o){
d = bi.divide(d).add(d).divide(BigInteger.valueOf(2));
if(last.equals(d))
break;
last = d;

}
System.out.println(d);
if (i != 1)
System.out.println();
}
}
}
}