给定整数 NNN，求 1≤x,y≤N1\le x, y\le N1≤x,y≤N 且 gcd(x,y)\gcd(x, y)gcd(x,y) 为素数的数对 (x,y)(x, y)(x,y) 有多少对。 输入格式 一个整数 NNN。 输出格式 一个整数，表示满足条件的数对个数。 样例输入 4 样例输出 4 样例解释 N=4N=4N=4 时，满足条件的数对为 (2,2),(2,4),(3,3),(4,2)(2,2), (2,4), (3,3), (4,2)(2,2),(2,4),(3,3),(4,2)。 数据范围 1≤N≤1071\le N\le 10^71≤N≤107。 来源与许可 本题题面与测试数据整理自 BZOJ 2818。