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:
20210306 09:28:39
majid, you've hammered so many TLE's, WA's and NZEC's that the 120submission long SPOJ history doesn't even fully show it, then you switched to CPP and proceeded to hit another 16 WA's and NZEC's before your first AC. I can't even imagine the stupor you find yourself in solving what you consider, as opposed to this, a difficult task, but are you really sure it's the problem that's stupid? 

majid:
20210306 08:31:47
I tried 1000000 ways to solve this STUPID problem in CSHARP but TLE after TLE...


sowmiksarker:
20200925 16:43:34
Finally solved it! Nice problem. 

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. 
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 