Minimum Coins with Power-of-Two Denominations

You are given a non-negative integer \(K\). Your task is to determine the minimum number of coins required to sum up to exactly \(K\) using coins whose denominations are powers of two, i.e., \(1, 2, 4, 8, \dots\). Note that if \(K = 0\), the answer is 0.

The optimal strategy is to use the largest coin (power of two) that does not exceed \(K\) repeatedly until \(K\) becomes zero. In other words, the answer is equivalent to counting the number of 1's in the binary representation of \(K\) (also called the Hamming weight).

You are required to handle multiple queries. The program should first read an integer \(T\) representing the number of test cases, followed by \(T\) lines each containing an integer \(K\). For every query, print the minimum number of coins needed on a separate line.

inputFormat

The input is read from standard input and has the following format:

T
K1
K2
...
KT

where \(T\) is the number of queries, and each \(K_i\) (\(0 \le K_i \le 10^{9}\)) represents a query.

outputFormat

For each query, output the minimum number of coins required. Each answer should be printed on a new line to standard output.

## sample

4
6
10
15
1023

2
2
4
10

</p>