The average of averages is not always the average.

VegiCat has just learned about segment trees and wants to practice using them.

For a positive integer $n$, he considers the sequence $a_i = i$ ($1 \le i \le n$). He decides to build a segment tree to answer range average queries on this sequence.

In VegiCat's segment tree, each node corresponds to an interval $[l, r]$ and stores a value $v_{l,r}$, which VegiCat intends to represent the average over that interval. The root corresponds to the entire interval $[1, n]$.

However, VegiCat mistakenly assumes that a parent interval's average always equals the average of the values stored in its two child nodes. Therefore, he adds the values stored in the two child nodes and divides the sum by $2$.

VegiCat first constructs the segment tree by calling $\text{Build}(1, n)$. After the segment tree has been built, he answers a query for an interval $[L, R]$ by calling $\text{Query}(1, n, L, R)$. The two recursive procedures are given in Algorithm 1.

Algorithm 1 Build and Query

$$ \begin{array}{rl} 1: & \textbf{procedure } \text{Build}(l, r) \\ 2: & \quad \textbf{if } l = r \textbf{ then} \\ 3: & \quad \quad v_{l,l} \leftarrow a_l \\ 4: & \quad \quad \textbf{return} \\ 5: & \quad \textbf{end if} \\ 6: & \quad m \leftarrow \left\lfloor \dfrac{l + r}{2} \right\rfloor \\ 7: & \quad \text{Build}(l, m) \\ 8: & \quad \text{Build}(m + 1, r) \\ 9: & \quad v_{l,r} \leftarrow \dfrac{v_{l,m} + v_{m+1,r}}{2} \\ 10: & \textbf{end procedure} \\[6pt] 11: & \textbf{procedure } \text{Query}(l, r, L, R) \\ 12: & \quad \textbf{if } L \le l \textbf{ and } r \le R \textbf{ then} \\ 13: & \quad \quad \textbf{return } v_{l,r} \\ 14: & \quad \textbf{end if} \\ 15: & \quad m \leftarrow \left\lfloor \dfrac{l + r}{2} \right\rfloor \\ 16: & \quad \textbf{if } R \le m \textbf{ then} \\ 17: & \quad \quad \textbf{return } \text{Query}(l, m, L, R) \\ 18: & \quad \textbf{else if } L > m \textbf{ then} \\ 19: & \quad \quad \textbf{return } \text{Query}(m + 1, r, L, R) \\ 20: & \quad \textbf{end if} \\ 21: & \quad x \leftarrow \text{Query}(l, m, L, R) \\ 22: & \quad y \leftarrow \text{Query}(m + 1, r, L, R) \\ 23: & \quad \textbf{return } \dfrac{x + y}{2} \\ 24: & \textbf{end procedure} \end{array} $$

Although VegiCat's algorithm is incorrect in general, it returns the correct average for some intervals. Count the number of such intervals.

For an interval $[L, R]$, its true average is

$$ \frac{\sum_{i=L}^{R} a_i}{R - L + 1}. $$

More precisely, count the number of pairs $(L, R)$ satisfying $1 \le L \le R \le n$ such that

$$ \text{Query}(1, n, L, R) = \frac{\sum_{i=L}^{R} a_i}{R - L + 1}. $$

All averages are computed as exact rational numbers, without rounding or truncation.

Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), the number of test cases. The description of the test cases follows.

Each of the next $T$ lines contains one integer $n$ ($1 \le n \le 10^6$), the length of the sequence.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^6$.

Output

For each test case, output an integer — the number of intervals $[L, R]$ for which VegiCat's query procedure returns exactly the true average.

Examples

Input 1

3
1
5
14

Output 1

1
10
35

Note

For the second test case, $n = 5$, there are $10$ valid intervals:

$$ \begin{aligned} &[1, 1],\ [1, 2],\ [2, 2],\ [2, 3],\ [2, 5], \\ &[3, 3],\ [3, 4],\ [4, 4],\ [4, 5],\ [5, 5]. \end{aligned} $$

For example, querying $[2, 5]$ returns

$$ \frac{\frac{2+3}{2} + \frac{4+5}{2}}{2} = \frac{7}{2}, $$

which equals the true average of $2, 3, 4, 5$. Thus, $[2, 5]$ is counted.

In contrast, querying $[1, 5]$ returns

$$ \frac{\frac{\frac{1+2}{2}+3}{2} + \frac{4+5}{2}}{2} = \frac{27}{8}, $$

while its true average is $3$. Thus, $[1, 5]$ is not counted.