Alice was a bright student of Mathematics. She loved the properties of right-angled triangles. However, she was not able to do her mathematics homework. She is given an integer $$X$$. She is interested in finding out the number of right-angled triangles with $$X$$ as one of its sides. A right-angled triangle can be uniquely determined by its sides. Also, the order of sides does not matter. So a triangle with sides (3, 4, 5) is the same as a triangle with sides (4, 3, 5).

She suspected that this is not a mathematics problem but rather a programming task. So she asks her friend Bob for help.

Input format

The first line contains a single integer $$T (1\leq T \leq10)$$, the number of test cases.
The only line of each test case contains a single integer $$X (1\leq X \leq10^{12})$$.

Output format

Print $$T$$ lines each containing one integer that is the total number of right-angled triangles with $$X$$ as one of its sides.