This problem is a programming version of Problem 131 from projecteuler.net
There are some prime values, , for which there exists a positive integer, , such that the expression is a perfect cube.
For example, when , .
What is perhaps most surprising is that for each prime with this property the value of is unique, and there are only four such primes below one-hundred.
How many primes below have this remarkable property?
Input Format
The first line of input contains , the number of test cases.
Each test case consists of one line containing a single integer, .
Constraints
But for test cases worth 50% of the total score:
Output Format
For each test case, output a single line containing a single integer, the answer for that test case.
Sample Input
2
5
100
Sample Output
0
4