Boards

Interview

Time limit1sMemory limit128 MB

Summary

From the smallest power of two at least K, find the fewest board halvings so some pieces sum to exactly K.

Level: Medium5 of 10
Topics: Bit manipulation, Greedy
Solved: No attempts yet

Problem

Captain Pitt wants to build a fence. To do that he needs boards whose lengths add up to exactly $K$ .

He has only two things to work with:

A machine that cuts any single board into two equal halves.
One starting board whose length is a power of two that he gets to choose (a carpenter friend delivers it).

Each cut takes one board and turns it into two boards of half its length. Beginning from that single power-of-two board, find the minimum number of cuts needed so that some subset of the boards he ends up with has lengths summing to exactly $K$ .

Input

The first line contains the number of test cases $Z$ ( $1 \le Z \le 10$ ).

Each of the next $Z$ lines contains one integer $K$ ( $1 \le K \le 10^{12}$ ): the total board length Captain Pitt needs in that test case.

Output

For each test case, print a single integer on its own line: the minimum number of cuts Captain Pitt has to make.

Examples1

Example 1
Input
```
2
3
4
```
Expected output
```
2
0
```