GCD

题目描述

给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的数对(x,y)有多少对.

输入输出格式

输入格式


一个整数N

输出格式


答案

输入输出样例

输入样例 #1

4

输出样例 #1

4

说明

对于样例(2,2),(2,4),(3,3),(4,2) 1<=N<=10^7 来源:bzoj2818 本题数据为洛谷自造数据,使用[CYaRon](https://github.com/luogu-dev/cyaron)耗时5分钟完成数据制作。