Diga cuantos números enteros de ~1~ a ~n (1 \leq n \leq 10^{12})~, tienen una cantidad impar de divisores.

Tenga en cuenta que ~b~ es un divisor de ~a~, si existe un número entero ~k~, tal que ~b \cdot k = a~.

Usted tendrá que procesar ~T (1 \leq T \leq 10^4)~ casos de prueba en cada caso.

Entrada

Un entero ~T~ en la primera línea, la cantidad de casos a procesar.

A continuación ~T~ líneas cada una con un entero, ~n_{i}~.

Salida

Un solo entero solo en una línea en cada caso, la cantidad de números enteros de ~1~ a ~n_{i}~, que tienen una cantidad impar de divisores.

Puntuación

No habra puntuación parcial en este problema.

Ejemplo de entrada

3
1
2
5

Ejemplo de salida

1
1
2