i have been trying alot but cant comeup with a solution,i thought using segmented sieve but it gives tle. https://www.spoj.com/problems/BSPRIME/

BSPRIME — Binary Sequence of Prime Number no tags 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...

Input The first line is an integer T(1 ≤ T ≤ 50,000), denoting the number of test cases. Then, T test cases follow.

For each test case, there is an integer N(0 ≤ N ≤ 150,000,000) written in one line.

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

Example Input: 3 3 10 50

Output: 2 8 36