ค่าเฉลี่ยของค่าเฉลี่ยไม่ได้เท่ากับค่าเฉลี่ยเสมอไป

VegiCat เพิ่งได้เรียนรู้เกี่ยวกับเซกเมนต์ทรี (segment tree) และต้องการฝึกฝนการใช้งาน

สำหรับจำนวนเต็มบวก $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]$ จึงไม่ถูกนับรวม