La media delle medie non è sempre la media.

VegiCat ha appena imparato gli alberi di segmenti e vuole esercitarsi a usarli.

Per un intero positivo $n$, considera la successione $a_i = i$ ($1 \le i \le n$). Decide di costruire un albero di segmenti per rispondere a query sulla media di un intervallo su questa successione.

Nell'albero di segmenti di VegiCat, ogni nodo corrisponde a un intervallo $[l, r]$ e memorizza un valore $v_{l,r}$, con cui VegiCat intende rappresentare la media su tale intervallo. La radice corrisponde all'intero intervallo $[1, n]$.

Tuttavia, VegiCat assume erroneamente che la media di un intervallo padre sia sempre uguale alla media dei valori memorizzati nei suoi due nodi figli. Pertanto, somma i valori memorizzati nei due nodi figli e divide la somma per $2$.

VegiCat costruisce innanzitutto l'albero di segmenti chiamando $\text{Build}(1, n)$. Dopo che l'albero di segmenti è stato costruito, risponde a una query per un intervallo $[L, R]$ chiamando $\text{Query}(1, n, L, R)$. Le due procedure ricorsive sono riportate nell'Algoritmo 1.

Algoritmo 1 Costruzione e 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} $$

Sebbene l'algoritmo di VegiCat sia errato in generale, restituisce la media corretta per alcuni intervalli. Conta il numero di tali intervalli.

Per un intervallo $[L, R]$, la sua media effettiva è

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

Più precisamente, conta il numero di coppie $(L, R)$ che soddisfano $1 \le L \le R \le n$ tali che

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

Tutte le medie sono calcolate come numeri razionali esatti, senza arrotondamenti o troncamenti.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^4$), il numero di casi di test. Segue la descrizione dei casi di test.

Ciascuna delle successive $T$ righe contiene un intero $n$ ($1 \le n \le 10^6$), la lunghezza della successione.

È garantito che la somma di $n$ su tutti i casi di test non supera $2 \cdot 10^6$.

Output

Per ogni caso di test, stampa un intero — il numero di intervalli $[L, R]$ per i quali la procedura di query di VegiCat restituisce esattamente la media effettiva.

Esempi

Input 1

3
1
5
14

Output 1

1
10
35

Nota

Per il secondo caso di test, $n = 5$, ci sono $10$ intervalli validi:

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

Ad esempio, la query su $[2, 5]$ restituisce

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

che è uguale alla media effettiva di $2, 3, 4, 5$. Pertanto, $[2, 5]$ viene contato.

Al contrario, la query su $[1, 5]$ restituisce

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

mentre la sua media effettiva è $3$. Pertanto, $[1, 5]$ non viene contato.