Bài 5: Thế giới Phân số tối giản

Yêu cầu: Cho số nguyên dương ~N~. Hãy đếm xem có bao nhiêu phân số ~\frac{a}{b}~ tối giản thỏa mãn điều kiện ~1 \le a < b \le N~.

Giới hạn:

• ~1 \le N \le 10^6~
• Thời gian: 1.0s | Bộ nhớ: 256 MB

Dữ liệu vào (Input):

• Chứa một số nguyên dương ~N~ duy nhất.

Dữ liệu ra (Output):

• In ra một số nguyên duy nhất là số lượng phân số tối giản thỏa mãn.

Ví dụ: Input:

5

Output:

9

(Giải thích: Các phân số tối giản là ~\frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \frac{3}{4}, \frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}~. Có tất cả ~9~ phân số.)