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.