Apple的爱好

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

Apple勤奋学习,尤其对数字很感兴趣。如4=2^28=2^39=3^2等,因此他很想知道在不超过n的范围内有多少个这样的数mm可以写成a^b (b>1)。你能帮助他吗?

Input

第一行输入T个测试样例 以下T行每行输入一个数n(0 < n <= 10^8)

Output

对于每个测试样例,输出相应的测试结果。

Sample Input

2
4
10

Sample Output

2
4

Hint

Source

StSky

提交代码