Given a number N calculate the number R of different presentations of N in the form A×A+B×B with A and B being positive integers including zero. 1×1+2×2 and 2×2+1×1 are not different presentations. So for input 5 the output is 1.

Input

Fifty tests with one positive integer < 10⁹.

Output

Print the illustrated above number R for each test.

Example

Input:
5
7
986244509
Output:
1
0
2