C. Kaosar Loves Binomials
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Your friend Kaosar asked you to solve a problem.

He will give you an integer $$$n$$$ and a function $$$Q(n,m)$$$, where $$$$$$Q(n,m)=(x+\frac{1}{x^m})^n$$$$$$

He asked you to calculate the sum of all integers $$$m$$$ for which $$$Q(n,m)$$$ has a nonzero constant term.

Input

The first line of the input will contain a single integer $$$t$$$ $$$(1 \le t \le 10^3)$$$ denoting the total number of test cases.

Next $$$t$$$ lines will contain a single integer $$$n$$$ $$$(1 \le n \le 10^9)$$$.

Output

Print the sum of all integers $$$m$$$ for which $$$Q(n,m)$$$ has a nonzero constant term.

Example
Input
3
1
2
3
Output
0
1
2
Note

In the first test case, only $$$m=0$$$ is valid.

  • $$$Q(1,0)=x+1$$$. Here $$$1$$$ is the constant term.

In the second test case, $$$m=0$$$ and $$$m=1$$$ are valid.

  • $$$Q(2,0)=x^2 + 2x + 1$$$ . Here $$$1$$$ is the constant term.
  • $$$Q(2,1)=x^2+x^{-2}+2$$$. Here $$$2$$$ is the constant term.