GCD

题目描述

给定正整数 $n$,求 $1\le x,y\le n$ 且 $\gcd(x,y)$ 为素数的数对 $(x,y)$ 有多少对。

输入输出格式

输入格式


只有一行一个整数,代表$n$。

输出格式


一行一个整数表示答案。

输入输出样例

输入样例 #1

4

输出样例 #1

4

说明

#### 样例输入输出 1 解释 对于样例,满足条件的 $(x,y)$ 为 $(2,2)$,$(2,4)$,$(3,3)$,$(4,2)$。 --- #### 数据规模与约定 - 对于 $100\%$ 的数据,保证 $1\le n\le10^7$。 --- 来源:bzoj2818。 本题数据为洛谷自造数据,使用 [CYaRon](https://github.com/luogu-dev/cyaron) 耗时 $5$ 分钟完成数据制作。