Meðaltal meðaltala er ekki alltaf meðaltalið.

VegiCat er nýbúinn að læra um biltré (segment trees) og vill æfa sig í að nota þau.

Fyrir jákvæða heiltölu $n$ skoðar hann rununa $a_i = i$ ($1 \le i \le n$). Hann ákveður að smíða biltré til að svara fyrirspurnum um meðaltal á bili í þessari runu.

Í biltré VegiCats samsvarar hver hnútur bili $[l, r]$ og geymir gildi $v_{l,r}$, sem VegiCat ætlar að tákni meðaltalið yfir það bil. Rótin samsvarar öllu bilinu $[1, n]$.

Hins vegar gerir VegiCat ranglega ráð fyrir að meðaltal foreldrisbils sé alltaf jafnt meðaltali gildanna sem geymd eru í tveimur barnahnútum þess. Því leggur hann saman gildin sem geymd eru í barnahnútunum tveimur og deilir summunni með $2$.

VegiCat smíðar fyrst biltréð með því að kalla á $\text{Build}(1, n)$. Eftir að biltréð hefur verið smíðað svarar hann fyrirspurn fyrir bil $[L, R]$ með því að kalla á $\text{Query}(1, n, L, R)$. Endurkvæmu aðferðirnar tvær eru gefnar í Reikniriti 1.

Reiknirit 1 Smíði og Fyrirspurn

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

Þótt reiknirit VegiCats sé rangt almennt séð skilar það réttu meðaltali fyrir sum bil. Teljið fjölda slíkra bila.

Fyrir bil $[L, R]$ er raunverulegt meðaltal þess

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

Nákvæmar tiltekið, teljið fjölda para $(L, R)$ sem uppfylla $1 \le L \le R \le n$ þannig að

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

Öll meðaltöl eru reiknuð sem nákvæmar ræðar tölur, án námundunar eða afskurðar.

Inntak

Fyrsta línan inniheldur heiltölu $T$ ($1 \le T \le 10^4$), fjölda prófunartilfella. Lýsing á prófunartilfellunum fylgir.

Hver af næstu $T$ línum inniheldur eina heiltölu $n$ ($1 \le n \le 10^6$), lengd rununnar.

Tryggt er að summa $n$ yfir öll prófunartilfelli fari ekki yfir $2 \cdot 10^6$.

Úttak

Fyrir hvert prófunartilfelli skal prenta heiltölu — fjölda bila $[L, R]$ þar sem fyrirspurnaraðferð VegiCats skilar nákvæmlega raunverulega meðaltalinu.

Dæmi

Inntak 1

3
1
5
14

Úttak 1

1
10
35

Athugasemd

Fyrir annað prófunartilfellið, $n = 5$, eru $10$ gild bil:

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

Til dæmis skilar fyrirspurn á $[2, 5]$

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

sem jafngildir raunverulegu meðaltali talnanna $2, 3, 4, 5$. Því er $[2, 5]$ talið með.

aftur á móti skilar fyrirspurn á $[1, 5]$

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

á meðan raunverulegt meðaltal þess er $3$. Því er $[1, 5]$ ekki talið með.