Longest Sequence of Powers of Two

You are given a positive integer ( n ). Your task is to determine the length ( L ) of the unique sequence of distinct powers of two that sums up to ( n ). In other words, since every positive integer has a unique binary representation, you need to count the number of ones in the binary representation of ( n ). Formally, find ( L ) such that [ n = \sum_{i=1}^{L} 2^{a_i}, ] where every ( 2^{a_i} ) is a power of two and all are distinct.

For example, if ( n = 15 ), its binary representation is 1111 which has 4 ones, so the answer is 4.

inputFormat

Input is read from standard input. It consists of a single line containing one positive integer ( n ) (1 ( \leq n \leq 10^{12} )).

outputFormat

Output to standard output a single integer representing the number of terms in the sequence (i.e., the number of ones in the binary representation of ( n )).## sample

9

2