Weighing#3603

Weighing

1 second
128 megabytes
Easy

The Ukrainian men's national boxing team took first place in the overall team standings at the 2012 Olympic Games in London, surpassing the host nation, Great Britain, as well as traditional favorites such as Cuba, Poland, and Kazakhstan in both the number and quality of medals. Altogether, Ukrainian boxers earned five Olympic medals: two gold, one silver, and two bronze.

As is known, before boxing competitions, there is a weigh-in ceremony conducted by referees to determine the correct weight category in which an athlete will compete.

The young programmer Vasya became interested in the following question: suppose we weigh boxers using a balance scale and use two binary sets of weights: a gram set and a kilogram set. Clearly, the gram set is standard and consists of weights of , , , , , , , , , , and grams. The kilogram set is similar—only the weights are heavier, but there are fewer of them. For simplicity, in this problem, let's assume that, by a strange coincidence, it turned out at the last Olympics that the weight of every athlete could be determined exactly using only the kilogram set.

It is also known that at the 2012 Olympic Games, athletes lighter than kg or heavier than kg did not participate.

Help Vasya determine how many weights from the kilogram set he will need to weigh the next athlete, if Vasya tries to use the minimum possible number, and has only one set of weights at his disposal.

Input

A single natural number — the weight of the next athlete to be weighed.

Output

A single number — the number of weights Vasya needs in order to measure the weight.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading