The Duel of Binary Warriors

mzc's household boasts a large number of loyal servants. However, the arrival of cat, the unpredictable physical education teacher, has sparked a duel for control over these servants. mzc is enraged and challenges cat. Because cat's stamina is unstable, mzc devises a clever strategy to determine the minimum time required to win the duel.

The strategy is as follows: Given that mzc has \( n \) servants, the minimum time required is equal to the number of \( 1 \)s in the binary representation of \( n \). In other words, if we write \( n \) in base 2, the answer is the popcount of \( n \): \[ T(n)=\text{popcount}(n)=\sum_{i\ge0} [b_i=1], \] where \( b_i \) denotes the \( i\)th bit of \( n \).

Your task is to compute this minimum time.

inputFormat

The input consists of a single line containing a positive integer \( n \) (\(1 \le n \le 10^9\)).

outputFormat

Output a single integer representing the minimum time required, which is the count of \( 1 \)s in the binary representation of \( n \).

sample

1

1