You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Zoey is captured by a monster and trapped in a cage. KT is going to rescue her, but now a wall is in KT's way……

Description

Right in the middle of the door is a number with the way to open the door written below. Solving this problem opens the door: The gate will generate a number for you. What is the minimum number of operations times that the number X can be zero?

• If x has an even number of ones in binary, the least position will be XOR with 1 in binary.
• If x has an odd number of ones in binary, the highest bits (not includ prefix 0) will be XOR with 1 in binary.

KT hope everyone can help him calculate, finally open the door, complete the hero to save the United States

You only need to output the minimum number of operands

For XOR:

0 XOR 0=0

0 XOR 1=1

1 XOR 0=1

1 XOR 1=0

Input

The first line contains one integer $t (1 ≤ t≤10^6)$ — the number of test cases. Then t test cases follow.

Each test case consists of one lines. The first line contains one integers x $(1 ≤ x ≤ 10^{10})$

Output

output the minimum number of operands make x to zero

Samples

5
1
2
3
4
5

1
1
2
1
2

hint

When x=5, the binary form is: 101

• First operation：101 -> 100
• Second operation：100 -> 000

So,The sum operations is 2

Limitation

1s, 1024KiB for each test case.