Hàm Euler φ(n) là số lượng các số nguyên dương không vượt quá n và nguyên tố cùng nhau (\(gcd = 1\)) với n.

Công thức: Nếu \(n = p_1^{e_1} \times p_2^{e_2} \times \dots \times p_k^{e_k}\) thì: \(\phi(n) = n \times (1 - 1/p_1) \times (1 - 1/p_2) \times \dots \times (1 - 1/p_k)\)

Cho số nguyên dương N, hãy tính φ(1) + φ(2) + ... + φ(N).

Đầu vào

Một dòng duy nhất chứa số nguyên N (\(1 \le N \le 10^6\)).

Đầu ra

Một số nguyên duy nhất là tổng các giá trị φ(i) với \(1 \le i \le N\).

Ví dụ

Input:
6

Output:
12

Giải thích

φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2. Tổng = 12.

Ràng buộc & Subtasks