Орташалардың орташасы әрқашан орташа мән бола бермейді.

VegiCat жақында ғана кесінділер ағашын үйреніп, оны қолданып жаттыққысы келеді.

Оң бүтін $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}. $$

Дәлірек айтқанда, $1 \le L \le R \le n$ шартын қанағаттандыратын және төмендегі теңдік орындалатын $(L, R)$ жұптарының санын табыңыз:

$$ \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$ шамасынан аспайтынына кепілдік беріледі.

Шығыс деректер

Әрбір тест үшін бір бүтін санды — VegiCat-тың сұраныс процедурасы дәл нақты орташа мәнді қайтаратын $[L, R]$ кесінділерінің санын шығарыңыз.

Мысалдар

Кіріс деректер 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]$ есепке алынбайды.