A. Mystic Quest
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$. Your task is to count how many integers $$$x$$$ ($$$1 \le x \le n$$$) are mystic numbers. A number $$$x$$$ is called mystic if $$$$$$x,\ x^x,\ x^{(x^x)},\ x^{(x^{(x^x)})},\ x^{(x^{(x^{(x^x)})})},\ \ldots$$$$$$ are all perfect squares.

A perfect square is an integer that is the square of an integer. For example, $$$9 = 3^2$$$ is a perfect square, but $$$8$$$ and $$$14$$$ are not.

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le $$$ $$$10 ^ 3$$$). The description of the test cases follows.

A single line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^{6}$$$).

Output

For each test case, output a single integer — the number of mystic numbers.

Example
Input
2
2
5
Output
1
2
Note

In the first test case, there is exactly one value of $$$x$$$, which is $$$1$$$, that satisfies the conditions.