1.


/**
* Angewandte Mathematik, SS09, IFB 2C
* ACM Problem #10023 (SquareRoot)
* Link: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=12&page=show_problem&problem=964
*
* @author Christian Posselt
* @author Jonathan Schubert
* @version 1.0, 03/25/2009
*
* Status : Accepted
* Runtime: 0.430
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;

class Main
{
public static void main(String[] args) throws IOException
{
BufferedReader Reader = new BufferedReader(new InputStreamReader(System.in));
StringBuilder bu = new StringBuilder();
int amount = Integer.parseInt(Reader.readLine());
for(;amount > 0; amount --)
{
Reader.readLine();
BigInteger digit = new BigInteger(Reader.readLine());
bu.append(sqrt(digit));
bu.append("\n\n");
}
bu.deleteCharAt(bu.length()-1);
System.out.print(bu.toString());
}

public static BigInteger sqrt(BigInteger N)
{
//Special case zero
if(N.equals(BigInteger.ZERO))
return BigInteger.ZERO;

BigInteger closer = BigInteger.ZERO;

//first closer value
closer = N.shiftRight(N.bitLength()/2);
BigInteger last = BigInteger.ZERO;

//(n+1) = (a/n + n)/2 Algorithms Heros
while(!closer.equals(last))
{
last = BigInteger.ZERO;
last = last.add(closer);
BigInteger part = BigInteger.ZERO;
part = part.add(N);
part = part.divide(closer);
part = part.add(closer);
part = part.shiftRight(1);
closer = BigInteger.ZERO;
closer = closer.add(part);
}
return closer;
}
}