Trung bình của các trung bình không phải lúc nào cũng là trung bình.

VegiCat vừa mới học về cây phân đoạn (segment tree) và muốn luyện tập sử dụng chúng.

Với một số nguyên dương $n$, cậu xét dãy số $a_i = i$ ($1 \le i \le n$). Cậu quyết định xây dựng một cây phân đoạn để trả lời các truy vấn trung bình đoạn trên dãy số này.

Trong cây phân đoạn của VegiCat, mỗi nút tương ứng với một đoạn $[l, r]$ và lưu một giá trị $v_{l,r}$, mà VegiCat dự định dùng để biểu diễn giá trị trung bình trên đoạn đó. Nút gốc tương ứng với toàn bộ đoạn $[1, n]$.

Tuy nhiên, VegiCat lại nhầm tưởng rằng giá trị trung bình của một đoạn cha luôn bằng trung bình cộng của hai giá trị lưu ở hai nút con của nó. Do đó, cậu cộng các giá trị lưu ở hai nút con lại rồi chia tổng đó cho $2$.

Đầu tiên VegiCat xây dựng cây phân đoạn bằng cách gọi $\text{Build}(1, n)$. Sau khi cây phân đoạn đã được xây dựng, cậu trả lời một truy vấn cho đoạn $[L, R]$ bằng cách gọi $\text{Query}(1, n, L, R)$. Hai thủ tục đệ quy này được cho trong Thuật toán 1.

Thuật toán 1 Xây dựng và Truy vấn

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

Mặc dù thuật toán của VegiCat nhìn chung là không chính xác, nhưng nó vẫn trả về giá trị trung bình đúng cho một số đoạn. Hãy đếm số lượng các đoạn như vậy.

Đối với một đoạn $[L, R]$, giá trị trung bình thực sự của nó là

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

Chính xác hơn, hãy đếm số cặp $(L, R)$ thỏa mãn $1 \le L \le R \le n$ sao cho

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

Tất cả các giá trị trung bình đều được tính dưới dạng số hữu tỉ chính xác, không làm tròn hay cắt bỏ phần thập phân.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $T$ ($1 \le T \le 10^4$), là số lượng bộ dữ liệu. Mô tả của các bộ dữ liệu theo sau.

Mỗi dòng trong $T$ dòng tiếp theo chứa một số nguyên $n$ ($1 \le n \le 10^6$), là độ dài của dãy số.

Dữ liệu đảm bảo tổng của $n$ trong tất cả các bộ dữ liệu không vượt quá $2 \cdot 10^6$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên — số lượng đoạn $[L, R]$ mà thủ tục truy vấn của VegiCat trả về chính xác giá trị trung bình thực sự.

Ví dụ

Dữ liệu vào 1

3
1
5
14

Dữ liệu ra 1

1
10
35

Ghi chú

Ở bộ dữ liệu thứ hai, $n = 5$, có $10$ đoạn hợp lệ:

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

Ví dụ, truy vấn $[2, 5]$ trả về

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

bằng với giá trị trung bình thực sự của $2, 3, 4, 5$. Do đó, $[2, 5]$ được tính.

Ngược lại, truy vấn $[1, 5]$ trả về

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

trong khi giá trị trung bình thực sự của nó là $3$. Do đó, $[1, 5]$ không được tính.