Arrange the Bricks!

You have $N$ bricks two dimensional bricks of the dimension $1 \times 2$. The bricks are rotatable i.e. you can turn the brick of dimension $1 \times 2$ into $2 \times 1$. Now, you have to determine how many different rectangular shapes can you create by arranging the bricks. Two rectangular shapes are different if their dimensions are different. There should be no space left in the rectangular shapes that you create with the bricks i.e they must be filled with bricks.

Note: Dimension $a \times b$ and $b \times a$ considered same.

Input

In the first line, there will be an integer $T$, the number of testcases.

In the next $T$ lines, there will be an integer $N$, indicating the number of bricks you will receive.

For Subtask 1: (30 points)

• $1 \le T \le 1000$
• $1 \le N \le 10000$

For Subtask 2: (30 points)

• $1 \le T \le 100$
• $1 \le N \le 10^{12}$

For Subtask 3: (40points)

• $1 \le T \le 100$
• $1 \le N \le 10^{14}$

Output

For each $N$, print the number of ways you can arrange the bricks.

Sample

4
1
2 
3 
4

1
2
2
2