平均の平均は必ずしも平均とは限らない。

VegiCat はセグメント木を学んだばかりで、それを使う練習をしたいと思っています。

正の整数 $n$ に対して、彼は数列 $a_i = i$ ($1 \le i \le n$) を考えます。彼はこの数列に対する区間平均クエリに答えるためにセグメント木を構築することにしました。

VegiCat のセグメント木では、各ノードは区間 $[l, r]$ に対応し、値 $v_{l,r}$ を保持します。VegiCat はこれがその区間の平均を表すことを意図しています。根は区間全体 $[1, n]$ に対応します。

しかし、VegiCat は親区間の平均が常にその 2 つの子ノードに保持されている値の平均に等しいと誤って思い込んでいます。そのため、彼は 2 つの子ノードに保持されている値を足し合わせ、その和を $2$ で割ります。

VegiCat はまず $\text{Build}(1, n)$ を呼び出してセグメント木を構築します。セグメント木が構築された後、区間 $[L, R]$ に対するクエリには $\text{Query}(1, n, L, R)$ を呼び出して答えます。これら 2 つの再帰手続きをアルゴリズム 1 に示します。

アルゴリズム 1 構築とクエリ

$$ \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} $$

VegiCat のアルゴリズムは一般には正しくありませんが、いくつかの区間に対しては正しい平均を返します。そのような区間の個数を数えてください。

区間 $[L, R]$ に対して、その真の平均は

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

より正確には、$1 \le L \le R \le n$ を満たす組 $(L, R)$ であって、次を満たすものの個数を数えてください：

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

すべての平均は丸めや切り捨てを行わず、正確な有理数として計算されます。

入力

1 行目にはテストケースの個数を表す整数 $T$ ($1 \le T \le 10^4$) が与えられます。続いてテストケースの記述が与えられます。

続く $T$ 行のそれぞれには、数列の長さを表す 1 つの整数 $n$ ($1 \le n \le 10^6$) が与えられます。

すべてのテストケースにおける $n$ の総和は $2 \cdot 10^6$ を超えないことが保証されます。

出力

各テストケースについて、VegiCat のクエリ手続きが真の平均を正確に返すような区間 $[L, R]$ の個数を表す整数を出力してください。

入出力例

入力例 1

3
1
5
14

出力例 1

1
10
35

注記

2 番目のテストケース $n = 5$ では、条件を満たす区間は次の $10$ 個です：

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

例えば、$[2, 5]$ に対するクエリは

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

を返し、これは $2, 3, 4, 5$ の真の平均に等しいです。したがって、$[2, 5]$ は数えられます。

一方、$[1, 5]$ に対するクエリは

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

を返しますが、その真の平均は $3$ です。したがって、$[1, 5]$ は数えられません。