cho.sh

Stick

Simulate repeatedly halving and discarding pieces of a 64 cm stick until the remaining pieces sum to X, then count how many pieces are glued together.

Medium4Bit manipulationSimulationMathNo attempts yetTime limit2sMemory limit128 MB

Problem

Jimin has a stick that is 64 cm long. One day, he wants a stick that is exactly X cm long. He plans to cut the original stick into smaller sticks and then glue some of them together.

The easiest way to cut a stick is to cut it in half. Jimin uses the following process.

  1. Add up the lengths of all sticks he currently has. At first, he has only one 64 cm stick. If the sum is greater than X, repeat the following steps.

    1. Cut the shortest stick he has in half.
    2. If throwing away one of the two halves would still leave a total length of at least X, throw away one of those halves.

  2. Glue all remaining sticks together to make a stick of length X cm.

Given X, determine how many sticks are glued together after this process.

Input

The first line contains X. X is a natural number not greater than 64.

Output

Print the number of sticks that are glued together to make X cm after the described process.