Type: Default 2000ms 256MiB

Heroic rescue

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(1t106)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 (1x1010)(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.

第三届SWPUACM新生赛-正式赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
12
Start at
2021-10-24 13:00
End at
2021-10-24 18:00
Duration
5 hour(s)
Host
Partic.
65