Given a non-negative integer 'n', compute and return the square root of 'n'. If n is not a perfect square, return the floor of the result.

Note: Do not use the in-built methods to calculate square root or power.

Expected Time Complexity: O(log n)

Example

n: 16
Answer: 4

n: 12
Answer: 3

n: 0
Answer: 0

Testing

Input Format

The first line contains 'T' denoting the no. of test cases.

Next T lines each contain a number 'n'.

Output Format

T lines each contain an integer denoting the square root of the number.

Sample Input

3
16
12
0

Expected Output

4
3
0

Constraints

0 <= T <= 5*105

0 <= n <= 108