Efficient Algotithms 2022

Znajdź część całkowitą pierwiastka podanej liczby.

Find the integer part of the square root of the given number.

Input

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita, oznaczająca liczbę zestawów danych, które za chwilę pojawią się na wejściu. Daną wejściową jest jedna liczba całkowita n, przy czym n jest nieujemna i na pewno nie większa niż liczba, którą w postaci dziesiętnej można przedstawić za pomocą 255 dziewiątek.

The first line of input contains one integer, denoting the number of data sets that are about to come in. The input data is one integer n, where n is non-negative and not greater than a number that can be represented in decimal form by 255 nines.

Output

Program ma wypisać część całkowitą pierwiastka tej liczby.

The program should print out the integer part of the square root of this number.

Example

Input:
4
2
9
101 
1023

Output:
1
3
10
31