El promedio de los promedios no siempre es el promedio.

VegiCat acaba de aprender sobre árboles de segmentos y quiere practicar su uso.

Para un entero positivo $n$, considera la sucesión $a_i = i$ ($1 \le i \le n$). Decide construir un árbol de segmentos para responder consultas de promedio de rango sobre esta sucesión.

En el árbol de segmentos de VegiCat, cada nodo corresponde a un intervalo $[l, r]$ y almacena un valor $v_{l,r}$, con el cual VegiCat pretende representar el promedio en ese intervalo. La raíz corresponde a todo el intervalo $[1, n]$.

Sin embargo, VegiCat asume erróneamente que el promedio de un intervalo padre siempre es igual al promedio de los valores almacenados en sus dos nodos hijos. Por lo tanto, suma los valores almacenados en los dos nodos hijos y divide la suma entre $2$.

VegiCat primero construye el árbol de segmentos llamando a $\text{Build}(1, n)$. Después de haber construido el árbol de segmentos, responde a una consulta para un intervalo $[L, R]$ llamando a $\text{Query}(1, n, L, R)$. Los dos procedimientos recursivos se presentan en el Algoritmo 1.

Algoritmo 1 Construcción y Consulta

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

Aunque el algoritmo de VegiCat es incorrecto en general, devuelve el promedio correcto para algunos intervalos. Cuenta el número de dichos intervalos.

Para un intervalo $[L, R]$, su promedio verdadero es

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

Más precisamente, cuenta el número de pares $(L, R)$ que satisfacen $1 \le L \le R \le n$ tales que

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

Todos los promedios se calculan como números racionales exactos, sin redondeo ni truncamiento.

Entrada

La primera línea contiene un entero $T$ ($1 \le T \le 10^4$), el número de casos de prueba. A continuación sigue la descripción de los casos de prueba.

Cada una de las siguientes $T$ líneas contiene un entero $n$ ($1 \le n \le 10^6$), la longitud de la sucesión.

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $2 \cdot 10^6$.

Salida

Para cada caso de prueba, imprime un entero — el número de intervalos $[L, R]$ para los cuales el procedimiento de consulta de VegiCat devuelve exactamente el promedio verdadero.

Ejemplos

Entrada 1

3
1
5
14

Salida 1

1
10
35

Nota

Para el segundo caso de prueba, $n = 5$, hay $10$ intervalos válidos:

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

Por ejemplo, consultar $[2, 5]$ devuelve

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

lo cual es igual al promedio verdadero de $2, 3, 4, 5$. Por lo tanto, $[2, 5]$ se cuenta.

En cambio, consultar $[1, 5]$ devuelve

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

mientras que su promedio verdadero es $3$. Por lo tanto, $[1, 5]$ no se cuenta.