← 返回题目列表

AtCoder · arc184_b

B. 123 套

中文机器翻译题面 查看原题

分数: 700 点

问题陈述

给你一个正整数 N。有一个空集 S,并且您可以执行任意多次以下操作:

  • 选择任意正整数 x。对于每个 x, 2x,和 3x,将其添加到 S 如果尚未存在 S.

找出满足以下条件所需的最少操作数 \{1, 2, \dots, N\} \subseteq S.

约束

  • 1 \leq N \leq 10^{9}

输入

输入由标准输入按以下格式给出:

N

输出

在一行中打印答案。


示例输入 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