Count Numbers with Exactly 3 Divisors

If a positive integer has exactly 3 positive divisors, it must be the square of a prime. For each given upper bound x, output how many such numbers do not exceed x.

This site adds a standard input/output protocol.

输入格式

The first line contains q (1 ≤ q ≤ 100000), followed by q lines with one integer x each (1 ≤ x ≤ 25000000000000).

输出格式

For each query, output on its own line the number of positive integers from 1 to x (inclusive) that have exactly 3 positive divisors.

样例 1

输入：

2
10
15

输出：

2
2

样例 2

输入：

1
100

输出：

4

样例 3

输入：

3
4
9
49

输出：

1
2
4