You are a lover of bacteria. You want to raise some bacteria in a box. 

Initially, the box is empty. Each morning, you can put any number of bacteria into the box. And each night, every bacterium in the box will split into two bacteria. You hope to see exactly *x* bacteria in the box at some moment. 

What is the minimum number of bacteria you need to put into the box across those days?
The only line containing one integer *x* (1 ≤ *x* ≤ 10<sup class="upper-index">9</sup>).
from sys import stdin; inp = stdin.readline
from math import dist, ceil, floor, sqrt, log
from collections import defaultdict, Counter, deque
def IA(sep=' '): return list(map(int, inp().split(sep)))
def QA(sep=' '): return deque(map(int, inp().split(sep)))
def FA(): return list(map(float, inp().split()))
def SA(): return inp().split()
def I(): return int(inp())
def F(): return float(inp())
def S(): return input()
def O(l:list): return ' '.join(map(str, l))
def geo_term(n:int, a:int, r:int): return a*pow(r, (n-1))
def get_geo_term(x:int, a:int, r:int):
    p = (log(x)-log(a)+log(r)) / log(r)
    f = floor(p); c = ceil(p)
    return f, c 
def is_geo_term(x:int, a:int, r:int):
    f, c = get_geo_term(x, a, r)
    return any([geo_term(p, a, r) == x for p in [f,c]])

def main():
    n = I()
    c = 1 
    if is_geo_term(n, 1, 2): 
        return c 
    else: 
        position = get_geo_term(n, 1, 2)[0]
        term = geo_term(position, 1, 2 )
        c += n-term 
        return c

if __name__ == '__main__':
    print(main())