La moyenne des moyennes n'est pas toujours la moyenne.

VegiCat vient d'apprendre les arbres de segments et souhaite s'entraîner à les utiliser.

Pour un entier strictement positif $n$, il considère la suite $a_i = i$ ($1 \le i \le n$). Il décide de construire un arbre de segments afin de répondre à des requêtes de moyenne sur un intervalle sur cette suite.

Dans l'arbre de segments de VegiCat, chaque nœud correspond à un intervalle $[l, r]$ et stocke une valeur $v_{l,r}$, par laquelle VegiCat entend représenter la moyenne sur cet intervalle. La racine correspond à l'intervalle entier $[1, n]$.

Cependant, VegiCat suppose à tort que la moyenne d'un intervalle parent est toujours égale à la moyenne des valeurs stockées dans ses deux nœuds enfants. Par conséquent, il additionne les valeurs stockées dans les deux nœuds enfants et divise la somme par $2$.

VegiCat construit d'abord l'arbre de segments en appelant $\text{Build}(1, n)$. Une fois l'arbre de segments construit, il répond à une requête pour un intervalle $[L, R]$ en appelant $\text{Query}(1, n, L, R)$. Les deux procédures récursives sont données dans l'Algorithme 1.

Algorithme 1 Construction et Requête

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

Bien que l'algorithme de VegiCat soit incorrect en général, il renvoie la moyenne exacte pour certains intervalles. Comptez le nombre de tels intervalles.

Pour un intervalle $[L, R]$, sa vraie moyenne est

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

Plus précisément, comptez le nombre de couples $(L, R)$ vérifiant $1 \le L \le R \le n$ tels que

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

Toutes les moyennes sont calculées comme des nombres rationnels exacts, sans arrondi ni troncature.

Entrée

La première ligne contient un entier $T$ ($1 \le T \le 10^4$), le nombre de cas de test. La description des cas de test suit.

Chacune des $T$ lignes suivantes contient un entier $n$ ($1 \le n \le 10^6$), la longueur de la suite.

Il est garanti que la somme de $n$ sur l'ensemble des cas de test ne dépasse pas $2 \cdot 10^6$.

Sortie

Pour chaque cas de test, affichez un entier — le nombre d'intervalles $[L, R]$ pour lesquels la procédure de requête de VegiCat renvoie exactement la vraie moyenne.

Exemples

Entrée 1

3
1
5
14

Sortie 1

1
10
35

Note

Pour le deuxième cas de test, $n = 5$, il y a $10$ intervalles valides :

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

Par exemple, la requête sur $[2, 5]$ renvoie

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

ce qui est égal à la vraie moyenne de $2, 3, 4, 5$. Ainsi, $[2, 5]$ est compté.

En revanche, la requête sur $[1, 5]$ renvoie

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

alors que sa vraie moyenne est $3$. Ainsi, $[1, 5]$ n'est pas compté.