SP11844 BSPRIME - Binary Sequence of Prime Number

Binary Sequence of Prime Number is a binary sequence that created by converting prime number to base-2 (Without leading zeros): (2) $ _{10} $ =(10) $ _{2} $ (3) $ _{10} $ =(11) $ _{2} $ (5) $ _{10} $ =(101) $ _{2} $ (7) $ _{10} $ =(111) $ _{2} $ ... If all base-2 of prime number joined, then we get the binary sequence like this: 10111011111011110110... Now your task is to count how many digit '1' appear in the first **N** terms of the sequence, example: \-->If N=3, digit '1' appear 2 times: 101110... \-->If N=10, digit '1' appear 8 times: 1011101111101...

The first line is an integer **T**(1 T T test cases follow. For each test case, there is an integer **N**(0 N

For each test case, output the number of digit '1' appear in the first **N** terms of the sequence