Minimum Number of Checks

You are given a total amount T and need to determine the minimum number of checks required to sum up to T. Each check's value must be a power of 2 (i.e., 1, 2, 4, 8, ...). This task is equivalent to counting the number of 1's in the binary representation of T (also known as the Hamming weight). In addition, you are to process multiple amounts, stopping when the value 0 is encountered (0 is not processed).

For example, when T = 23, its binary form is 10111 which contains 4 ones, so the answer is 4.

inputFormat

The input consists of several lines. Each line contains a single integer T. You will process each number until you encounter a line with the integer 0, which marks the end of input. The number 0 should not be processed.

Example:

23
37
1024
0

outputFormat

For each input amount (except the terminating 0), output the minimum number of checks required. The results should be printed in one line separated by a single space.

## sample

23
37
1024
0

4 3 1

</p>