Sum of Pleasantness Values

Given an odd positive integer \( k \) (with \(1\leq k < 2^{64}\)), consider all odd numbers from \(1\) to \(k\) inclusive. For an odd integer \(x\), its pleasantness value \(f(x)\) is defined as the unique positive integer \(m\) such that \(x\) is one of the \(m\) consecutive odd numbers in the representation of \(m^3\) as a sum of \(m\) consecutive odd numbers. More precisely, it is known that

[ m^3=\underbrace{\bigl(m^2-m+1\bigr)+\bigl(m^2-m+3\bigr)+\cdots+\bigl(m^2+m-1\bigr)}_{m;\text{terms}}. ]

Thus, for any odd (x), we have (f(x)=m) if and only if

[ m^2-m+1\le x\le m^2+m-1, \quad x\text{ odd}. ]

For example, (f(21)=5) since (5^3=21+23+25+27+29), (f(11)=3) and (f(3)=2).

Now, define the sum

[ s = \sum_{x \text{ odd},\ 1\le x\le k} f(x) = f(1)+f(3)+\cdots+f(k). ]

Your task is to compute (s \bmod (10^9+7)). Note that the input contains multiple test cases.

inputFormat

The first line contains an integer \(T\) denoting the number of test cases. Each of the following \(T\) lines contains one positive odd integer \(k\) (\(1\leq k < 2^{64}\)).

outputFormat

For each test case, output one line containing \(s \bmod (10^9+7)\), where \(s\) is the sum of the pleasantness values of all odd integers from \(1\) to \(k\).

sample

4
1
3
7
11

1
3
8
14