该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

李普东倒下了。。。

众所周知，他是要 AKIOI 的男人，但是他在数论倒下了，但是他还喜欢数论算法，因此有了这个题。

题目描述

最近，普东 同学在寒假中学习了新课题 —— 欧几里得算法。

当发现 $a \cdot b = \text{lcm}(a, b) \cdot \text{gcd}(a, b)$ 时，他有些惊讶。其中 $\text{gcd}(a, b)$ 是 $a$ 和 $b$ 的 最大公约数 ，而 $\text{lcm}(a, b)$ 是最小公倍数 (LCM)。

普东 想到既然 LCM 和 GCD 的乘积存在，或许它们的商也值得研究：

例如，他取 $a = 2$ 和 $b = 4$，计算得到 $F(2, 4) = \frac{4}{2} = 2$，结果是一个质数（一个数如果恰好有两个因数则为质数）！

• 现在他认为当 $a < b$ 且 $F(a, b)$ 是质数时，这个比值 $F(a, b)$ 是 有趣的比值。

由于 普东 刚接触数论，他需要你帮忙计算 —— 满足 $F(a, b)$ 是 有趣的比值 且 $1 \leq a < b \leq n$ 的不同数对 $(a, b)$ 有多少个？

输入格式

第一行输入一个整数 $n$。

输出格式

输出一个整数，代表满足条件 $1 \leq a < b \leq n$ 的 有趣比值 $F(a, b)$ 的数量。

5

4

10

11

34

49

10007

24317

提示

样例解释

自己打表

数据范围

对于 $100\%$ 的范围，满足 $2\leq n\leq 10^7$。

• 子任务 1（30 分）：保证 $n\leq 100$。
• 子任务 2（30 分）：保证 $n\leq 2000$。
• 子任务 3（30 分）：保证 $n\leq 2\cdot 10^5$。
• 子任务 4（10 分）：保证 $n\leq 10^7$。