/ 
実行時間制限: 8 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
正整数 N が与えられます。空集合 S があり、あなたは以下の操作を何回でも行うことができます。
- 正整数 x を自由に選ぶ。x, 2x, 3x それぞれについて、もし S に含まれなければ追加する。
\{1, 2, \dots ,N\} \subseteq S を満たすまでに必要な操作回数の最小値を求めてください。
制約
- 1 \leq N \leq 10^{9}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを 1 行に出力せよ。
入力例 1
7
出力例 1
4
1, 2, 5, 7 を選ぶことで S = \{1, 2, 3, 4, 5, 6, 7, 10, 14, 15, 21\} となり条件を満たします。3 回以下の操作で条件を満たすことはできません。
入力例 2
25
出力例 2
14
Score : 700 points
Problem Statement
You are given a positive integer N. There is an empty set S, and you can perform the following operation any number of times:
- Choose any positive integer x. For each of x, 2x, and 3x, add it to S if it is not already in S.
Find the minimum number of operations required to satisfy \{1, 2, \dots, N\} \subseteq S.
Constraints
- 1 \leq N \leq 10^{9}
Input
The input is given from Standard Input in the following format:
N
Output
Print the answer in one line.
Sample Input 1
7
Sample Output 1
4
Choosing 1, 2, 5, and 7 yields S = \{1, 2, 3, 4, 5, 6, 7, 10, 14, 15, 21\}, which satisfies the condition. It is impossible to satisfy the condition with three or fewer operations.
Sample Input 2
25
Sample Output 2
14