Project Euler #131: Prime cube partnership

_{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