← 返回题目列表

Codeforces · 10/C

C. 数字根

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

不久前,Billy遇到了这样一个问题,给定[1, N]范围内的三个自然数A、B和C,要求检查方程AB = C是否正确。最近比利研究了数字的数字根的概念。需要提醒您的是,数字 x 的数字根 d(x) 是该数字所有数字的和 s(x),如果 s(x) ≤ 9,则为 d(s(x))。例如,数字 6543 的数字根计算如下: d(6543) = d(6 + 5 + 4 + 3) = d(18) = 9。 Billy 计算出数字乘积的数字根等于因子数字根乘积的数字根,即 d(xy) = d(d(x)d(y))。他想到了以下解决问题的方法:计算数字根并检查是否满足这个条件。然而,比利怀疑这个条件是否足够。这就是为什么他要求你找出给定问题的测试示例的数量,这样比利提出的算法就会出错。

输入

第一行包含唯一的数字 N (1 ≤ N ≤ 106)。

输出

输出一个数字——[1, N]范围内所需的A、B、C的数量。

示例

输入 #1

4

输出 #1

2

输入 #2

5

输出 #2

6

注意

对于第一个样本,所需的三元组是 (3, 4, 3) 和 (4, 3, 3)。