题目描述

斯捷潘应聘的公司正在开发一种新的超可靠加密算法 RSA-SUPER。斯捷潘了解到，RSA 是以 Rivest、Shamir 和 Adleman 三人的姓氏命名的公开密钥密码算法。RSA 密码系统是第一个既可用于加密又可用于数字签名的系统，并被大量密码学应用使用，包括 PGP、S/MIME、TLS/SSL、IPsec/IKE 等。

众所周知，RSA 算法的基础是使用一对质数 $P$ 和 $Q$，并形成数 $N=P\times Q$。数 $P$ 和 $Q$ 被称为加密密钥，数 $N$ 被称为加密模数。质数是恰好有两个不同正因子的自然数：$1$ 和它本身。

新算法 RSA-SUPER 与 RSA 的根本区别在于密钥的选择。RSA 算法需要一对质数 $P$ 和 $Q$，而 RSA-SUPER 中的 $P$ 和 $Q$ 只需要互质。两个自然数称为互质，当且仅当它们除了 $1$ 之外没有公共因子。

为了分析新算法的可靠性，公司负责人想知道有多少对不同的密钥 $P,Q$，满足 $1<P<Q$，并且对应的加密模数满足 $N\le K$。这项并不简单的任务交给了斯捷潘，而他当然请求你帮助。

输入格式

第一行包含一个整数 $K$。

满足：$1 \le K \le 10^9$。

输出格式

输出一个整数，表示不同密钥对 $P,Q$ 的数量。

评分说明

原题给出的部分分限制如下：

• $K \le 300$：不少于 $20$ 分；
• $K \le 1000$：不少于 $30$ 分；
• $K \le 5000$：不少于 $40$ 分；
• $K \le 10^5$：不少于 $50$ 分；
• $K \le 10^6$：不少于 $60$ 分。

样例 1

12

3

样例 2

18

6

样例解释

第一个样例中的密钥对为：$(2,3)$、$(2,5)$、$(3,4)$。

第二个样例中的密钥对为：$(2,3)$、$(2,5)$、$(2,7)$、$(2,9)$、$(3,4)$、$(3,5)$。