Minimum Farcoins

You are given an amount of money X and coins with denominations that are powers of 2, i.e. \(1,2,4,8,\dots\). Your task is to determine the minimum number of Farcoins required to exactly pay the sum \(X\). In other words, you need to represent \(X\) as the sum of the fewest possible coins, where each coin's value is \(2^k\) for some non-negative integer \(k\).

Example: For \(X = 10\), the binary representation is \(1010_2\), which means \(10 = 8 + 2\), so the minimum number of coins is 2.

This is essentially equivalent to counting the number of 1s in the binary representation of \(X\). Use this observation to implement an efficient solution.

inputFormat

The input is given from standard input (stdin) with the following format:

• The first line contains an integer \(T\) (\(1 \le T \le 10^5\)), representing the number of test cases.
• Each of the following \(T\) lines contains an integer \(X\) (\(1 \le X \le 10^9\)), representing the amount of money for that test case.

outputFormat

For each test case, output a single line containing the minimum number of Farcoins required to form the amount \(X\).

## sample

3
10
37
1024

2
3
1

</p>