April Fools Contest 2017 B

Description

Programmers' kids solve this riddle in 5-10 minutes. How fast can you do it?

Input

The input contains a single integer n (0 ≤ n ≤ 2000000000).

Output

Output a single integer.

Examples

input

11

output

2

input

14

output

0

input

61441

output

2

input

571576

output

10

input

2128506

output

3
化成16进制，然后数圈圈

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s;
int a,b,c,d;
int main()
{
    int ans;
    cin>>ans;
    if(ans==0)
    {
        a++;
    }
    while(ans)
    {
        if(ans%16==10)
        {
            a++;
        }
        else if(ans%16==11)
        {
            a+=2;
        }
        else if(ans%16==13)
        {
            a++;
        }
        else if(ans%16==6)
        {
            a++;
        }
        else if(ans%16==8)
        {
            a+=2;
        }
        else if(ans%16==9)
        {
            a++;
        }
        else if(ans%16==0)
        {
            a++;
        }
        else if(ans%16==4)
        {
            a++;
        }
        ans/=16;
    }
    cout<<a<<endl;
    return 0;
}