Luigi has N balls. The balls look identical. However, there is one ball that is heavier. The rest share the same weight. Luigi is so cool he has a balance to weigh the balls.
At each weighing he can choose two disjoint subsets of balls and compare them.
Luigi wants to compute the minimum number of weighings after which he is 100% sure which ball is the special one.
Input
The first line of the input contains an integer N denoting the number of balls.
Output
The only line of output should contain an integer denoting the minimum number of weighings after which he is 100% sure which ball is the heavier one.
Restrictions
- 1 ≤ N ≤ 1018
- Two sets are disjoint if and only if they have no element in common.
Sample
Input | Output | Explanation |
---|---|---|
2 | 1 | We can compare the two balls and see which one is heavier. |
4 | 2 | We can make 2 groups of 2 balls each and decide which is heavier. Then, we can split that group in 2 groups of 1 ball, compare them and decide which is the heavier among all. |
9 | 2 |