BSPRIME  Binary Sequence of Prime Number
Binary Sequence of Prime Number is a binary sequence that created by converting prime number to base2 (Without leading zeros):
(2)_{10}=(10)_{2}
(3)_{10}=(11)_{2}
(5)_{10}=(101)_{2}
(7)_{10}=(111)_{2}
...
If all base2 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
hide comments
nadstratosfer:
20180904 18:13:22
Unexpected AC with kindof a prototype of a solution. Began thinking about solving this one 3 days ago but didn't like my initial ideas; woke up with better ones and there we go. This is how the best problems work, forcing my brain to work on them even when I don't intend to =) 

hodobox:
20171010 21:04:34
I was running out of optimizations, but Eratosthenes barely made it through :P 

devendrap:
20160624 15:04:47
Till: 11753933 Last edit: 20160624 15:05:15 

vishu:
20150814 16:23:23
@Tjandra Sir can u please tell what improvents can I make in my code or I need to change my brute force approach?


Prakhar Gupta:
20140705 06:43:20
any hint???


[Lakshman]:
20140518 18:28:30
Finally Accepted.!!!!!!!!!! 

[Lakshman]:
20140330 11:13:57
@Tjandra Satria Gunawan can you please check why I am getting WA, Now I have correct algo with efficient prime computation up to MAX N. 

Ehor Nechiporenko:
20130106 20:34:14
Wow, @Tjandra, Thanks for this problems. It showed me how I can optimize my Sieve algos.


vaibhav:
20130103 06:42:06
output of 50 is 47 not 36


(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
20120928 10:58:49
Info: Changed cluster to 3GHz and mem limit to 1536 MB. Now 6 users accepted after rejudge. Last edit: 20120928 10:56:16 
Added by:  Tjandra Satria Gunawan 
Date:  20120712 
Time limit:  1s 
Source limit:  10000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM32GCC ASM64 MAWK BC CCLANG CPP14 CPP14CLANG COBOL COFFEE DCLANG DDMD DART ELIXIR FANTOM FORTH GOSU GRV JSMONKEY KTLN NIM NODEJS OBJC OBJCCLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET 
Resource:  Own Problem 