BSPRIME - Binary Sequence of Prime Number

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


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 NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem

hide comments
2022-10-05 12:16:12
easy one...
2022-10-05 12:15:28
peace of cake :)))
2022-07-26 21:07:58
can someone please help me,how to do this?
2021-03-06 09:28:39
majid, you've hammered so many TLE's, WA's and NZEC's that the 120-submission 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?
2021-03-06 08:31:47 majid
I tried 1000000 ways to solve this STUPID problem in CSHARP but TLE after TLE...
I switch to c++ and got ac in 0.32
Actually i think the problem is very very easy and i dont undrestand why there are less than 100 people who solve this STUPID problem.
Try this, it's EASY.
2020-09-25 16:43:34
Finally solved it! Nice problem.
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 =)
2017-10-10 21:04:34
I was running out of optimizations, but Eratosthenes barely made it through :P
2016-06-24 15:04:47
Till: 11753933

Last edit: 2016-06-24 15:05:15
2015-08-14 16:23:23 vishu
@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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.