SP123 PAYING - Paying in Byteland

There are infinitely many coin denominations in the Byteland. They have values of $2^i$ for $i=0$, $1, 2, ...$. We will say that set of coins $c_1, c_2, ..., c_k$ is perfect when it is possible to pay every amount of money between $0$ and $c_1+...+c_k$ using some of them (so ${4,2,2,1}$ is perfect while ${8,1}$ is not). The question is - is it always possible to change given sum n into a perfect set of coins? Of course it is possible ;). Your task will be more complicated: for a sum $n$ you should find minimal number of coins in its perfect representation.

First line of input contains one integer $c \le 50$ - number of test cases. Then $c$ lines follow, each of them consisting of exactly one integer $n \le 10^{1000}$.

For each test case output minimal number of coins.