Description

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.
2
9 = 7 + 2 × 1
2
15 = 7 + 2 × 2
2
21 = 3 + 2 × 3
2
25 = 7 + 2 × 3
2
27 = 19 + 2 × 2
2
33 = 31 + 2 × 1
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 N, print the number of ways N can be represented as a sum of prime and twice a square.
Example 15 can be represented in two ways as 15 = 7 + 2 × 22 and 15 = 13 + 2 × 12
Input Format
The first line contains an integer T , i.e., number of test cases.
Next T lines will contain an integer N.
Output Format
Print the values corresponding to each test case.
Constraints
1 ≤ T ≤ 100
5
9 ≤ N < 5 × 10
N ∈ {odd composite number}
Sample Input

Sample Output