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

 

See also: Another problem added by Tjandra Satria Gunawan


hide comments
nadstratosfer: 2018-09-04 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: 2017-10-10 21:04:34

I was running out of optimizations, but Eratosthenes barely made it through :P

devendrap: 2016-06-24 15:04:47

Till: 11753933

Last edit: 2016-06-24 15:05:15
vishu: 2015-08-14 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?
submission id:14891064

Prakhar Gupta: 2014-07-05 06:43:20

any hint???

[Lakshman]: 2014-05-18 18:28:30

Finally Accepted.!!!!!!!!!!

[Lakshman]: 2014-03-30 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: 2013-01-06 20:34:14

Wow, @Tjandra, Thanks for this problems. It showed me how I can optimize my Sieve algos.

By the way, if you like Number theory problems, you should be interest in HS12PRIM ;-))

Ans: Congratulations, and Thanks for your appreciation :-)

Last edit: 2013-01-06 23:18:30
vaibhav: 2013-01-03 06:42:06

output of 50 is 47 not 36
Ans: no, 36 is correct... read problem description carefully!

Last edit: 2013-01-03 11:06:28
(Tjandra Satria Gunawan)(曾毅昆): 2012-09-28 10:58:49

Info: Changed cluster to 3GHz and mem limit to 1536 MB. Now 6 users accepted after rejudge.

Last edit: 2012-09-28 10:56:16

Added by:Tjandra Satria Gunawan
Date:2012-07-12
Time limit:1s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC ASM64 MAWK BC C-CLANG CPP14-CLANG CPP14 COBOL COFFEE D-DMD D-CLANG DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem