Square root

The Problem

You are to determinate X by given Y, from expression

The Input

The first line is the number of test cases, followed by a blank line.

Each test case of the input contains a positive integer Y (1<=Y<=10¹⁰⁰⁰), with no blanks or leading zeroes in it.
It is guaranteed, that for given Y, X will be always an integer.

Each test case will be separated by a single line.

The Output

For each test case, your program should print X in the same format as Y was given in input.

Print a blank line between the outputs for two consecutive test cases.

Sample Input

1

7206604678144

Sample Output

2684512

import java.util.Scanner;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);
		String x;
		BigInteger l, r, m, n;
		int t = keyboard.nextInt();
		while(t != 0) {
			t--;
			x = keyboard.next();
			n = new BigInteger(x);
			l = BigInteger.valueOf(1);
			r = BigInteger.valueOf(10).pow(x.length()/2+1);
			m = BigInteger.valueOf(0);
			while(l.compareTo(r) <= 0) {
				m = l.add(r).shiftRight(1);
				if(m.multiply(m).compareTo(n) == 1) {
					r = m.subtract(BigInteger.valueOf(1));
				} else if(m.multiply(m).compareTo(n) == -1) {
					l = m.add(BigInteger.valueOf(1));
				} else
					break;
			}
			if(m.multiply(m).compareTo(n) > 0)
				m = l.subtract(BigInteger.valueOf(1));
			System.out.println(m.toString());
			if(t != 0)
				System.out.println("");
		}
	}
}