Once upon a time in childhood, we all enjoyed playing the game "Pebbles" or "Five pebbles", as someone called it. For the game, ordinary pebbles were needed, which could easily be found on the street. It was possible to play anywhere;
The first step of the game was as follows. All five pebbles are thrown to the ground in front of them. One of them was chosen. This is a cue ball. This pebble is thrown into the air and while it flies, it is necessary to pick up one of the pebbles remaining on the ground and have time to catch the flying one with the same hand. The picked up pebble is set aside and the action is repeated for all remaining pebbles.
In the following steps, the number of pebbles to pick up increases. The last step was the exam, when it was necessary to throw all the collected pebbles into the air and catch them with the back of the hand, and then toss again and catch them with the open palm. How many pebbles in the end remained, so many points you get. The turn passes to the next player, who also repeats all the steps. Then a new round of the game was launched. The winner was the one who scored the most points for all rounds.
A lot of guys made the game difficult in all sorts of ways.
Let's say the guys have an infinite number of pebbles lying on the ground. At the end of the round, they do not need to catch all the pebbles in their palms, but exactly enough so that their total number of points increases by 1 or doubles or triples. Before the start of the game, everyone already has 1 point. The winner will be the one who gets
N points faster.
Let's assume that all players have enough playing experience, and they always reach the exam with the number of stones they need (so that they can increase the required number of points by 1, double or triple).
Determine the minimum number of rounds you need to play in order to get the given number of points
N from
1 .
Input
The program receives a single number as input, not exceeding 106.
Output
You need to print one number: the least number of operations you are looking for.
Examples
| # |
Input |
Output |
| 1 |
1 |
0 |
| 2 |
5 |
3 |
| 3 |
32718 |
17 |