The Game of Two

Sharan, the brave boy, is currently standing at the origin (0,0). He is taking part in The Game of Two. In each round of this game, he is given an integer n and he is asked to reach (n,0) in minimum number of jumps.

There are a few of rules of this game. They are :

1. In each jump, he can jump along the x-axis either forward or backward.
2. Direction of each of his jump is independent of the direction of the previous ones.
3. Length of each of his jump must be a power of two.
4. Length of each of his jump must be strictly greater than the length of the previous ones.

Sharan, though a brave boy, is not smart enough.
Can you please help him figure out the minimum number of jumps he needs to reach his goal ?

Input

The first line contains a single integer q, number of rounds. (1 <= q <= 105).
Then q lines follow. Each of them contains an integer n. (1 <= n <= 109).

Output

Output contains q lines.
ith line contains the minimum number of jumps needed in the ith round.

Sample

Input	Output
3 8 11 15	1 3 2

Sample Case Explanation :

8 = 23
11 = 23 + 22 - 20
15 = 24 - 21