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
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
himanshu jain: 2012-09-28 10:58:49

how many prime number will be reqd to make 150000000 length string?

Ans: More than 100000000 less than 150000000

Last edit: 2012-08-22 15:39:28
Ehor Nechiporenko: 2012-09-28 10:58:49

Good problem, but unfortunantly Atkin Sieve gets TLE ((

Zhouxing Shi: 2012-09-28 10:58:49

nice


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 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD 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