Gjennomsnittet av gjennomsnitt er ikke alltid gjennomsnittet.

VegiCat har nettopp lært om segmenttrær og ønsker å øve på å bruke dem.

For et positivt heltall $n$ betrakter han følgen $a_i = i$ ($1 \le i \le n$). Han bestemmer seg for å bygge et segmenttre for å svare på spørringer om intervallgjennomsnitt på denne følgen.

I VegiCats segmenttre tilsvarer hver node et intervall $[l, r]$ og lagrer en verdi $v_{l,r}$, som VegiCat har til hensikt at skal representere gjennomsnittet over dette intervallet. Roten tilsvarer hele intervallet $[1, n]$.

VegiCat antar imidlertid feilaktig at et foreldreintervalls gjennomsnitt alltid er lik gjennomsnittet av verdiene som er lagret i de to barnenodene. Derfor legger han sammen verdiene som er lagret i de to barnenodene og deler summen på $2$.

VegiCat konstruerer først segmenttreet ved å kalle $\text{Build}(1, n)$. Etter at segmenttreet er bygget, svarer han på en spørring for et intervall $[L, R]$ ved å kalle $\text{Query}(1, n, L, R)$. De to rekursive prosedyrene er gitt i Algoritme 1.

Algoritme 1 Bygg og Spør

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

Selv om VegiCats algoritme er feil generelt, returnerer den riktig gjennomsnitt for noen intervaller. Tell antallet slike intervaller.

For et intervall $[L, R]$ er det sanne gjennomsnittet

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

Mer presist, tell antallet par $(L, R)$ som oppfyller $1 \le L \le R \le n$ slik at

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

Alle gjennomsnitt beregnes som eksakte rasjonale tall, uten avrunding eller avkorting.

Inndata

Den første linjen inneholder et heltall $T$ ($1 \le T \le 10^4$), antallet testtilfeller. Beskrivelsen av testtilfellene følger.

Hver av de neste $T$ linjene inneholder ett heltall $n$ ($1 \le n \le 10^6$), lengden på følgen.

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $2 \cdot 10^6$.

Utdata

For hvert testtilfelle, skriv ut et heltall — antallet intervaller $[L, R]$ der VegiCats spørreprosedyre returnerer nøyaktig det sanne gjennomsnittet.

Eksempler

Inndata 1

3
1
5
14

Utdata 1

1
10
35

Merk

For det andre testtilfellet, $n = 5$, er det $10$ gyldige intervaller:

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

For eksempel returnerer en spørring på $[2, 5]$

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

som er lik det sanne gjennomsnittet av $2, 3, 4, 5$. Dermed telles $[2, 5]$.

Derimot returnerer en spørring på $[1, 5]$

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

mens det sanne gjennomsnittet er $3$. Dermed telles ikke $[1, 5]$.