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

无额外样例。

题目描述

给出一个整数 M，求满足以下条件的有序数对 (a,b) 的数量：

（1）1 ≤ a, b ≤ M；

（2）a 与 b 的最大公约数为质数。

输入

一个整数 M

输出

一个整数，表示答案。

样例1输入

5

样例1输出

5

样例1解释

有以下 5 个数对：(2,2),(2,4),(3,3),(4,2),(5,5)

样例2输入

1234567

样例2输出

419041287762

数据范围

$1 ≤ M ≤ 10^7$