Craiova

Task

In the stands of a match played by Universitatea Craiova, there are $N$ groups of supporters arranged in a linear manner, where each group $i$ ($1 \le i \le N$) initially consists of $i$ people.

A brawl between two adjacent groups of sizes $a$ and $b$ respectively will have the following consequences:

• If $a > b$, then the first group will remain with $a - b$ people, the second group will have $0$ people left, and the remaining people from the first group will occupy the section of the stands previously occupied by the second group.
• If $a < b$, then the second group will remain with $b - a$ people, the first group will have $0$ people left, and the remaining people from the second group will occupy the section of the stands previously occupied by the first group.
• If $a = b$, then both groups will leave (by mutual agreement) from the stadium, and the regions in the stands where these two groups were will be occupied by the neighboring groups (if they exist).

Starting from the initial state, how many groups can remain alone in the stands after a series of brawls?

Input data

Each test contains multiple test cases. The first line will contain the number of test cases $T$.

Each test case contains a single number $N$ - the number of groups in the stands.

Output data

For each test case, print the number of groups that can remain alone in the stands after a series of brawls, starting from the initial state.

Constraints and clarifications

• $1 \leq T \leq 2 \cdot 10^5$.
• $1 \leq N \leq 10^{18}$.

Example

stdin

5
4
5
8
11
12

stdout

1
3
4
7
8

Explanation

In the first test case, there are $4$ groups, with sizes $1$, $2$, $3$, and $4$ people respectively.
The only group that can remain alone in the stadium is group $4$, after the following series of brawls:

The above image pictures a series of brawls after which group $4$ remains alone in the stadium.
The numbers inside the cells represent the sizes of the groups, and the numbers above the cells represent the group controlling the respective region in the stands.

In the second test case, the groups that can remain alone in the stadium are $1$, $3$, and $5$.
A series of brawls after which group $1$ is the only one left is described below:

A series of brawls after which group $1$ remains alone in the stadium. In the last brawl, groups $2$ and $3$ have the same number of people, so they leave the stands by mutual agreement. The regions in the stands where groups $2$ and $3$ were are occupied by group $1$.

In the third test case, the groups that can remain alone in the stadium are $3$, $4$, $6$, and $8$.
In the fourth test case, the groups that can remain alone in the stadium are $3$, $4$, $5$, $6$, $7$, $9$, and $11$.
In the fifth test case, the groups that can remain alone in the stadium are $3$, $4$, $5$, $6$, $7$, $8$, $10$, and $12$.