평균의 평균이 항상 평균인 것은 아니다.

VegiCat은 방금 세그먼트 트리를 배웠고 이를 사용하는 연습을 하고 싶어 합니다.

양의 정수 $n$에 대해, 그는 수열 $a_i = i$ ($1 \le i \le n$)를 생각합니다. 그는 이 수열에서 구간 평균 쿼리에 답하기 위해 세그먼트 트리를 구축하기로 결정합니다.

VegiCat의 세그먼트 트리에서 각 노드는 구간 $[l, r]$에 대응하며, VegiCat이 해당 구간의 평균을 나타내도록 의도한 값 $v_{l,r}$을 저장합니다. 루트는 전체 구간 $[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]$는 개수에 포함되지 않습니다.