BITS - Counting Bits

no tags 

Given N, if we write all numbers from 1 to N (both inclusive) in binary what is the count of 1s I have written.

For example, if N=3, I will write down: 1, 10, 11. Therefore, a total of 4 ones.

Input

First line contains, T, the number of test cases. Each test case consists of one integer per line denoting N.

Output

Print the required answer.

Constraints

1 ≤ T ≤ 1000
1 ≤ N ≤ 1000

Example

Input:
1
3

Output:
4

Problem Setter: Lalit Kundu

Solve harder version here: BIT2.


hide comments
ivar.raknahs: 2014-02-22 15:34:55

easy with python

Anubhav Balodhi : 2014-02-16 08:38:12

The very basic of programming...

Rishav Goyal: 2014-02-13 04:50:55

try this after BITS , http://www.spoj.com/problems/BIT2

Last edit: 2014-02-08 15:35:00
Rishav Goyal: 2014-02-13 04:50:55

would be better raise the limit ~10^9 or more than that.

Aravindan Chandrasekaran: 2014-02-13 04:50:55

But I am getting WA ?

Jacob Plachta: 2014-02-13 04:50:55

I'm pretty sure that there are already problems on SPOJ that ask exactly this (or similar things), with larger bounds (like 10^9).
--ans(francky)--> I'm sure too. My search box isn't functional, so I can't give a link. Problem moved to tutorial.

Last edit: 2014-02-02 16:10:52
suryadev: 2014-02-13 04:50:55

Anybody is having better solution than O(N) or O(NlogN) ?

Bhavik: 2014-02-13 04:50:55

@aravindan: yes

Aravindan Chandrasekaran: 2014-02-13 04:50:55

Answer for 1000 is 4938 right ?


Added by:darkshadows
Date:2014-01-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64