This problem is a programming version of Problem 46 from projecteuler.net
It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.
It turns out that the conjecture was false as you'll discover some values can't be represented as a sum of prime and twice a square.
You are given , print the number of ways N can be represented as a sum of prime and twice a square.
Example can be represented in two ways as and
Input Format
The first line contains an integer , i.e., number of test cases.
Next lines will contain an integer .
Constraints
Output Format
Print the values corresponding to each test case.
Sample Input
2
9
15
Sample Output
1
2