题目描述

我们定义对于数对$(i, j)$, 如果存在$\frac{i}{gcd(i, j)}$ 和 $\frac{j}{gcd(i,j)}$ 都是质数，则称作神奇数对。

现在你需要求出对于任意 $i,j ≤ N$ 所组成的 (i, j) 有多少不同的神奇数对。

请注意，如果 $i_1 ≠ i_2$ 或 $j_1 ≠ j_2$，则对 $(i_1, j_1)$ 和对 $(i_2, j_2)$ 被视为不同的。

输入描述

输入仅有一行，包含一个整数 N.

$1 ≤ N ≤ 10^7$

输出描述

输出一个整数，表示有多少数对 $(i,j)$ 为神奇数对。

样例

样例输入#1

3

样例输出#1

2

样例输入#2

5

样例输出#2

6