The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:
Given an integer , Find out how many numbers less than or equal to are there that can be expressed as a sum of a prime square , prime cube and prime fourth power.
Input Format
First line contains an integer denoting the number of testcases.
The next lines contain integer .
Constraints
Output Format
The line containing the answer for the testcase.
Sample Input
1
50
Sample Output
4