In this problem you have to find the Square Root for given number. You may assume that such a number exist and it will be always an integer.

Solutions to this problem can be submitted in C, C++, Pascal, Algol, Fortran, Ada, Ocaml, Prolog, Whitespace, Brainf**k and Intercal only.

Input

t - the number of test cases [t <= 50]
then t positive numbers follow, each of them have up to 800 digits in decimal representation.

Output

Output must contain exactly t numbers equal to the square root for given numbers. See sample input/output for details.

Example

Input:
3
36
81
226576

Output:
6
9
476