Rata-rata dari rata-rata tidak selalu sama dengan rata-rata.

VegiCat baru saja mempelajari segment tree dan ingin berlatih menggunakannya.

Untuk suatu bilangan bulat positif $n$, ia meninjau barisan $a_i = i$ ($1 \le i \le n$). Ia memutuskan untuk membangun sebuah segment tree guna menjawab kueri rata-rata rentang pada barisan ini.

Dalam segment tree milik VegiCat, setiap simpul bersesuaian dengan suatu interval $[l, r]$ dan menyimpan sebuah nilai $v_{l,r}$, yang dimaksudkan VegiCat untuk menyatakan rata-rata pada interval tersebut. Akar bersesuaian dengan keseluruhan interval $[1, n]$.

Namun, VegiCat secara keliru mengasumsikan bahwa rata-rata interval induk selalu sama dengan rata-rata dari nilai yang disimpan pada kedua simpul anaknya. Oleh karena itu, ia menjumlahkan nilai yang disimpan pada kedua simpul anak lalu membagi jumlahnya dengan $2$.

VegiCat pertama-tama membangun segment tree dengan memanggil $\text{Build}(1, n)$. Setelah segment tree selesai dibangun, ia menjawab kueri untuk interval $[L, R]$ dengan memanggil $\text{Query}(1, n, L, R)$. Kedua prosedur rekursif tersebut diberikan pada Algoritma 1.

Algoritma 1 Build dan Query

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

Meskipun algoritma VegiCat secara umum tidak tepat, algoritma tersebut mengembalikan rata-rata yang benar untuk beberapa interval. Hitunglah banyaknya interval semacam itu.

Untuk suatu interval $[L, R]$, rata-rata sebenarnya adalah

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

Lebih tepatnya, hitunglah banyaknya pasangan $(L, R)$ yang memenuhi $1 \le L \le R \le n$ sedemikian sehingga

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

Semua rata-rata dihitung sebagai bilangan rasional eksak, tanpa pembulatan ataupun pemotongan.

Masukan

Baris pertama berisi sebuah bilangan bulat $T$ ($1 \le T \le 10^4$), yang menyatakan banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul di bawahnya.

Masing-masing dari $T$ baris berikutnya berisi satu bilangan bulat $n$ ($1 \le n \le 10^6$), yaitu panjang barisan.

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $2 \cdot 10^6$.

Keluaran

Untuk setiap kasus uji, keluarkan sebuah bilangan bulat — banyaknya interval $[L, R]$ yang membuat prosedur kueri VegiCat mengembalikan tepat rata-rata sebenarnya.

Contoh

Masukan 1

3
1
5
14

Keluaran 1

1
10
35

Catatan

Untuk kasus uji kedua, $n = 5$, terdapat $10$ interval yang valid:

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

Sebagai contoh, melakukan kueri pada $[2, 5]$ mengembalikan

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

yang sama dengan rata-rata sebenarnya dari $2, 3, 4, 5$. Dengan demikian, $[2, 5]$ ikut dihitung.

Sebaliknya, melakukan kueri pada $[1, 5]$ mengembalikan

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

sedangkan rata-rata sebenarnya adalah $3$. Dengan demikian, $[1, 5]$ tidak ikut dihitung.