Середнє середніх — це не завжди середнє.

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

Точніше, порахуйте кількість пар $(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]$ не враховується.