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

hide comments
vas14: 2020-01-16 02:51:56

Identical code that implements O(N) with fast I/O using getchar_unlocked():
CPP 14 TLE
C++ 4.3.2 WA
C (Clang 8) Accepted

nadstratosfer: 2019-01-19 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: 2018-11-03 21:02:57

Hi, I solved the problem in c++ with fast io and barely got the solution in time limit.
Can i maybe get a clue on improving my solution (or a push in the direction of other faster solution)?

kshubham02: 2018-07-04 12:17:52

@Morass O(N+Q) with fast IO is giving TLE... Can you please check it.. submission id is 21939386

Last edit: 2018-07-04 14:11:29
s_a_k_s_h_a_m: 2018-06-07 09:15:18

you can use 10^8 as dp array size , declare it global
faster i/o
since n is even so n-1 is odd, f(n*(n-1))=f(n).use __builtin_ffsl
use cube array to compute cubes
an easy one

totallynotan: 2018-04-17 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: 2017-08-19 02:47:54

@hodobox: Oh i see ^_^ Thanx!

hodobox: 2017-08-15 14:53:50

@morass: You added T(1) = 1, it should be T(1) = 0 :)

morass: 2017-07-16 16:53:05

@hodobox: Thank you, updated it .. ^_^

hodobox: 2017-07-16 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:2017-03-14
Time limit:0.800s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All