ממוצע של ממוצעים אינו תמיד הממוצע.

VegiCat למד זה עתה על עצי מקטעים (segment trees) ורוצה לתרגל את השימוש בהם.

עבור מספר שלם חיובי $n$, הוא מתבונן בסדרה $a_i = i$ ($1 \le i \le n$). הוא מחליט לבנות עץ מקטעים כדי לענות על שאילתות ממוצע טווח על סדרה זו.

בעץ המקטעים של VegiCat, כל צומת מתאים לקטע $[l, r]$ ושומר ערך $v_{l,r}$, אשר VegiCat מתכוון שייצג את הממוצע על אותו קטע. השורש מתאים לקטע כולו $[1, n]$.

אולם, VegiCat מניח בטעות שהממוצע של קטע אב תמיד שווה לממוצע הערכים השמורים בשני צומתי הבנים שלו. לכן, הוא מחבר את הערכים השמורים בשני צומתי הבנים ומחלק את הסכום ב-$2$.

VegiCat בונה תחילה את עץ המקטעים על ידי קריאה ל-$\text{Build}(1, n)$. לאחר שעץ המקטעים נבנה, הוא עונה על שאילתה עבור קטע $[L, R]$ על ידי קריאה ל-$\text{Query}(1, n, L, R)$. שתי הפרוצדורות הרקורסיביות נתונות באלגוריתם 1.

אלגוריתם 1 בנייה ושאילתה

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

למרות שהאלגוריתם של VegiCat אינו נכון באופן כללי, הוא מחזיר את הממוצע הנכון עבור חלק מהקטעים. ספרו את מספר הקטעים הללו.

עבור קטע $[L, R]$, הממוצע האמיתי שלו הוא

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

ליתר דיוק, ספרו את מספר הזוגות $(L, R)$ המקיימים $1 \le L \le R \le n$ כך שמתקיים

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

כל הממוצעים מחושבים כמספרים רציונליים מדויקים, ללא עיגול או קיצוץ.

קלט

השורה הראשונה מכילה מספר שלם $T$ ($1 \le T \le 10^4$), מספר מקרי הבדיקה. אחריה מופיע תיאור מקרי הבדיקה.

כל אחת מ-$T$ השורות הבאות מכילה מספר שלם אחד $n$ ($1 \le n \le 10^6$), אורך הסדרה.

מובטח כי סכום ערכי $n$ על פני כל מקרי הבדיקה אינו עולה על $2 \cdot 10^6$.

פלט

עבור כל מקרה בדיקה, הדפיסו מספר שלם — מספר הקטעים $[L, R]$ שעבורם פרוצדורת השאילתה של VegiCat מחזירה בדיוק את הממוצע האמיתי.

דוגמאות

קלט 1

3
1
5
14

פלט 1

1
10
35

הערה

עבור מקרה הבדיקה השני, $n = 5$, ישנם $10$ קטעים תקפים:

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

לדוגמה, שאילתה על $[2, 5]$ מחזירה

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

ששווה לממוצע האמיתי של $2, 3, 4, 5$. לכן, $[2, 5]$ נספר.

לעומת זאת, שאילתה על $[1, 5]$ מחזירה

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

בעוד שהממוצע האמיתי שלו הוא $3$. לכן, $[1, 5]$ אינו נספר.