ADAROBOT - Ada and CAPTCHA

Ada the Ladybug just got an innovative 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))3 + 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 definitely a 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 ≤ 106 , number of queries.

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

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

Added by:Morass
Date:2017-03-14
Time limit:0.800s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2017-07-06 18:27:31
learn about __builtin_ffsl easy one :P
2017-05-03 11:52:58
Ok thanks man anyway
EDIT: I did it without fast i/o

Last edit: 2017-05-04 22:51:58
2017-05-02 23:34:15
@ks1999: No clue :/ Seems the first part runs in 0.1 (and is independent of input) and the second part is "constant" - so unless there's mistake then it must be "IO" ... anyway I know nothing about pascal so it is hard for me to decide - sorry :'(

Have nice day
2017-05-02 17:09:37
i did a fast io and i think i have linear time. Don't know why am i getting TLE.

Last edit: 2017-05-02 18:45:54
2017-04-07 13:46:12
@sandip_coder:

A) The solution have lesser time - what you see is the summation of times for each test-file

B) O(N) per test-case is not enough

Good Luck!
2017-04-07 06:37:38
@morass why am i getting tle with O(n) solution as per test case?
2017-04-06 20:59:30
@morass you have given time limit as 0.8s but most of the accepted code having time more than 0.8s...why??
2017-03-28 13:26:55
@KD:
Firstly: It "runs" so it is not getting in cycle anywhere - it is "just slow" (and I guess it is not "very slow" - just a bit slower)
Secondly: I can say that slowest part of algorithm is this line "k=((ll)log2(k)) + 1;"

Even thought it is not intended nor optimal solution, it shall pass with a few optimizations :)

Good Luck

~/Morass
2017-03-28 13:15:18 KD
@morass can you Plzzzz check my solution .getting TLE ......
@morass Thanks for help..... Learn a lot about optimization

AC :) after so many TLE's.......
for loop giving TLE and while loop is getting accepted -_- (Seriously)......
fast I/O is required.......

Last edit: 2017-03-28 17:10:10
2017-03-28 12:24:13
@raj_rajvir: Hello

Consider following examples:

2: 10 (least significant bit on position 2, so 2 is returned)
3: 11 (least significant bit on position 1, so 1 is returned)
4: 100 (least significant bit on position 3, so 3 is returned)
5: 101 (least significant bit on position 1, so 1 is returned)
6: 110 (least significant bit on position 2, so 2 is returned)

Good Luck

~/Morass
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.