Ada the Ladybug just got an inovative idea (which might be a rival of captcha): She made following function - F(a)=least significant 1-bit of a (indexed from 1). She also made following recursive function T(N)=F(N*(N-1))³+T(N-2), where T(0)=0,T(1)=0.

Her idea is following- Instead of asking for captcha, she uses an opposite method: She gives you even N and you have to answer T(N) - if your answer is correct, then you are definetly robot and you won't be let in.

As her good friend she asked you to program a checker for her.

Input

The input begins with an integer 1 ≤ Q ≤ 10⁶ , number of queries.

The next Q lines contains an even integer: 2 ≤ N ≤ 2*10⁸

Output

For each query, print T(N)

Example Input

5
8
4
2
20
1000

Example Output

107
35
8
310
23988

Little explanation

F(2)=2
F(12)=3
F(30)=2
F(56)=4
F(90)=2
F(132)=3
F(182)=2
F(240)=5
F(306)=2
F(380)=3