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.