Minimum Powers of 2

You are given a non-negative integer \(N\). Your task is to find the minimum number of distinct powers of 2 required so that their sum equals \(N\). Equivalently, this is the same as counting the number of 1's in the binary representation of \(N\), because each 1 corresponds to a power of 2.

For example, if \(N = 7\), its binary representation is \(111\), so the answer is 3 since \(7 = 4 + 2 + 1\). Similarly, if \(N = 10\) (binary \(1010\)), the answer is 2, corresponding to \(8 + 2 = 10\).

inputFormat

The first line of input contains a single integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains one non-negative integer \(N\) (where \(0 \le N \le 2^{31}-1\)).

outputFormat

For each test case, output a single line containing the minimum number of powers of 2 that sum to \(N\>.

3
7
10
15

3
2
4