Problem Description

Given a positive integer $n$, count the number of pairs $(x, y)$ such that $1\le x, y\le n$ and $\gcd(x,y)$ is a prime number.

Input Format

A single line containing one integer representing $n$.

Output Format

Output a single integer in one line, representing the answer.

4

4

Hint

Sample Input/Output 1 Explanation

For the sample, the pairs $(x, y)$ that satisfy the condition are $(2, 2)$, $(2, 4)$, $(3, 3)$, $(4, 2)$.

Constraints

• For $100\%$ of the testdata, it is guaranteed that $1\le n\le 10^7$.

Source: bzoj2818.

The testdata for this problem are self-made by Luogu, generated using CYaRon, taking 5 minutes.

Translated by ChatGPT 5