Problem Description

In number theory for algorithm competitions, we have encountered algorithms such as the Sieve of Eratosthenes, the linear sieve, Möbius inversion, the Du Jiao sieve, the Powerful Number sieve, the Min_25 sieve, and the Zhou Ge sieve to help optimize the complexity of some summations or products. Now here comes the question: which of the above algorithms will be used in today’s problem?

Given a positive integer $n$, you need to compute

$$\sum\limits_{i=1}^n\sum\limits_{j=1}^n\lfloor \dfrac{n}{\max(i,j)}\rfloor [i \perp j]$$

where $[i \perp j]$ indicates whether $i$ and $j$ are coprime. That is, when $\gcd(i,j)=1$, the value of $[i \perp j]$ is $1$; otherwise, its value is $0$.

Input Format

One line contains a positive integer $n$ ($1\le n \le 10^9$).

Output Format

Output one line containing an integer, representing the result of the above summation.

2

4

Hint

Translated by ChatGPT 5