平均值嘅平均值唔一定等於平均值。

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]$ 唔會被計入。