CSETB - Count Set Bits


You are given a number n and you need to find the total number of set bits in the binary representation of all integers from 1 to n inclusive.

Input

The first line of input contains t denoting the number of test cases.

Next t lines contain a single integer n.

Constraints

  • 1 ≤ t ≤ 20
  • 1 ≤ n ≤ 104

Output

Output a single integer which is the total number of set bits in the binary representation of all integers from 1 to n inclusive.

Example

Input:
5
7
4
10
9
6

Output:
12
5
17
15
9

hide comments
nadstratosfer: 2021-06-02 00:25:55

Find the number of set bits in binary representations of all numbers from 1 to n, inslusive.


Added by:Samar
Date:2021-05-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All