ADAROBOT  Ada and CAPTCHA
Ada the Ladybug just got an inovative idea (which might be a rival of captcha): She made following function  F(a)=least significant 1bit of a (indexed from 1). She also made following recursive function T(N)=F(N*(N1))^{3}+T(N2), 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^{6} , number of queries.
The next Q lines contains an even integer: 2 ≤ N ≤ 2*10^{8}
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
hide comments
vas14:
20200116 02:51:56
Identical code that implements O(N) with fast I/O using getchar_unlocked():


nadstratosfer:
20190119 10:31:35
I got 4.00s simply following the tags; appreciate psetter for guidance as this approach is far more elegant than bruting it with 1.5GB mem usage. That being said, a better solution exists, also input is massive so *everything* that goes on in your program matters. Thanks to Morass for designing problems that provide multiple layers of fun =) 

dominikwis:
20181103 21:02:57
Hi, I solved the problem in c++ with fast io and barely got the solution in time limit.


kshubham02:
20180704 12:17:52
@Morass O(N+Q) with fast IO is giving TLE... Can you please check it.. submission id is 21939386 Last edit: 20180704 14:11:29 

s_a_k_s_h_a_m:
20180607 09:15:18
you can use 10^8 as dp array size , declare it global


totallynotan:
20180417 17:44:28
Again, :( O(N + QlogQ) doesn't pass under java even with fast I/O. Is switching to another language the only fix? 

morass:
20170819 02:47:54
@hodobox: Oh i see ^_^ Thanx! 

hodobox:
20170815 14:53:50
@morass: You added T(1) = 1, it should be T(1) = 0 :) 

morass:
20170716 16:53:05
@hodobox: Thank you, updated it .. ^_^ 

hodobox:
20170716 13:48:57
Hm, I think it could be mentioned that T(1) = 0. As far as I can tell you can't find it from the definition as it would require knowing T(1). 
Added by:  Morass 
Date:  20170314 
Time limit:  0.800s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 