Algorithms and Data Structures

Count Ones in Binary

You are given a single integer number . Your task is to count the number of 1s in the binary representation of and output this count.

Input

The first line contains a single integer ().

Output

A single integer: the number of 1s in the binary representation of .

Examples

Input
Output
5
2
1023
10

Constraints

Time limit: 2.4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in