- All Contests
- ProjectEuler+
- Project Euler #131: Prime cube partnership

# Project Euler #131: Prime cube partnership

# 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
```