متوسط المتوسطات ليس دائماً هو المتوسط.

تعلّم 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]$.