# #P1116. Heroic rescue

# Heroic rescue

# 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.