平均值的平均值並不總是等於平均值。

VegiCat 剛剛學會了線段樹，並想要練習使用它們。

對於正整數 $n$，他考慮序列 $a_i = i$（$1 \le i \le n$）。他決定建立一棵線段樹來回答此序列上的區間平均值查詢。

在 VegiCat 的線段樹中，每個節點對應一個區間 $[l, r]$ 並儲存一個值 $v_{l,r}$，VegiCat 打算用它來表示該區間的平均值。根節點對應整個區間 $[1, n]$。

然而，VegiCat 錯誤地假設父區間的平均值總是等於其兩個子節點中所儲存值的平均值。因此，他將兩個子節點中儲存的值相加並將總和除以 $2$。

VegiCat 首先透過呼叫 $\text{Build}(1, n)$ 來建構線段樹。在線段樹建構完成後，他透過呼叫 $\text{Query}(1, n, L, R)$ 來回答區間 $[L, R]$ 的查詢。這兩個遞迴程序如演算法 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}. $$

所有平均值均作為精確的有理數進行計算，不進行四捨五入或截斷。

輸入格式

第一行包含一個整數 $T$（$1 \le T \le 10^4$），代表測試資料的組數。接下來是各組測試資料的描述。

接下來的 $T$ 行中，每行包含一個整數 $n$（$1 \le n \le 10^6$），代表序列的長度。

保證所有測試資料中 $n$ 的總和皆不超過 $2 \cdot 10^6$。

輸出格式

對於每組測試資料，輸出一個整數——使得 VegiCat 的查詢程序恰好回傳真實平均值的區間 $[L, R]$ 的數量。

範例

範例輸入 1

3
1
5
14

範例輸出 1

1
10
35

說明

對於第二組測試資料，$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]$ 不會被計入。