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 ≤ 10⁴

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