Minimum Lunar Coins

You are given a positive integer \(n\). In the Lunar monetary system, the only available coin is of value 1 and its coins are magical: the minimum number of coins required to represent \(n\) is equal to the number of ones in the binary representation of \(n\). For example, if \(n=6\) its binary representation is \(110\) which has 2 ones, so the answer will be 2.

Your task is to compute the minimum number of Lunar Coins required to form the given amount \(n\). Your answer should be produced by reading the input from standard input and writing the result to standard output.

inputFormat

The input consists of a single integer \(n\) (where \(1 \le n \le 10^{9}\)).

outputFormat

Output a single integer: the minimum number of Lunar Coins needed, which is equivalent to the number of ones in the binary representation of \(n\).

6

2