Der Durchschnitt der Durchschnitte ist nicht immer der Durchschnitt.
VegiCat hat gerade Segmentbäume kennengelernt und möchte den Umgang mit ihnen üben.
Für eine positive ganze Zahl $n$ betrachtet er die Folge $a_i = i$ ($1 \le i \le n$). Er beschließt, einen Segmentbaum aufzubauen, um Bereichsdurchschnitts-Anfragen auf dieser Folge zu beantworten.
In VegiCats Segmentbaum entspricht jeder Knoten einem Intervall $[l, r]$ und speichert einen Wert $v_{l,r}$, der nach VegiCats Vorstellung den Durchschnitt über dieses Intervall darstellen soll. Die Wurzel entspricht dem gesamten Intervall $[1, n]$.
Jedoch nimmt VegiCat fälschlicherweise an, dass der Durchschnitt eines Elternintervalls immer gleich dem Durchschnitt der in seinen beiden Kindknoten gespeicherten Werte ist. Daher addiert er die in den beiden Kindknoten gespeicherten Werte und teilt die Summe durch $2$.
VegiCat konstruiert zunächst den Segmentbaum durch den Aufruf von $\text{Build}(1, n)$. Nachdem der Segmentbaum aufgebaut wurde, beantwortet er eine Anfrage für ein Intervall $[L, R]$ durch den Aufruf von $\text{Query}(1, n, L, R)$. Die beiden rekursiven Prozeduren sind in Algorithmus 1 angegeben.
Algorithmus 1 Aufbau und Anfrage
$$ \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} $$
Obwohl VegiCats Algorithmus im Allgemeinen falsch ist, liefert er für некоторые Intervalle den korrekten Durchschnitt. Zähle die Anzahl solcher Intervalle.
Für ein Intervall $[L, R]$ ist sein wahrer Durchschnitt
$$ \frac{\sum_{i=L}^{R} a_i}{R - L + 1}. $$
Genauer gesagt: Zähle die Anzahl der Paare $(L, R)$ mit $1 \le L \le R \le n$, sodass
$$ \text{Query}(1, n, L, R) = \frac{\sum_{i=L}^{R} a_i}{R - L + 1}. $$
Alle Durchschnitte werden als exakte rationale Zahlen berechnet, ohne Rundung oder Abschneiden.
Eingabe
Die erste Zeile enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die Anzahl der Testfälle. Es folgt die Beschreibung der Testfälle.
Jede der nächsten $T$ Zeilen enthält eine ganze Zahl $n$ ($1 \le n \le 10^6$), die Länge der Folge.
Es wird garantiert, dass die Summe von $n$ über alle Testfälle $2 \cdot 10^6$ nicht überschreitet.
Ausgabe
Gib für jeden Testfall eine ganze Zahl aus — die Anzahl der Intervalle $[L, R]$, für die VegiCats Anfrageprozedur exakt den wahren Durchschnitt zurückgibt.
Beispiele
Eingabe 1
3 1 5 14
Ausgabe 1
1 10 35
Hinweis
Für den zweiten Testfall, $n = 5$, gibt es $10$ gültige Intervalle:
$$ \begin{aligned} &[1, 1],\ [1, 2],\ [2, 2],\ [2, 3],\ [2, 5], \\ &[3, 3],\ [3, 4],\ [4, 4],\ [4, 5],\ [5, 5]. \end{aligned} $$
Beispielsweise liefert die Anfrage für $[2, 5]$
$$ \frac{\frac{2+3}{2} + \frac{4+5}{2}}{2} = \frac{7}{2}, $$
was dem wahren Durchschnitt von $2, 3, 4, 5$ entspricht. Somit wird $[2, 5]$ gezählt.
Im Gegensatz dazu liefert die Anfrage für $[1, 5]$
$$ \frac{\frac{\frac{1+2}{2}+3}{2} + \frac{4+5}{2}}{2} = \frac{27}{8}, $$
während sein wahrer Durchschnitt $3$ ist. Somit wird $[1, 5]$ nicht gezählt.