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 = p1^e1 × p2^e2 × ... × pk^ek thì: φ(n) = n × (1 - 1/p1) × (1 - 1/p2) × ... × (1 - 1/pk)

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 ≤ N ≤ 10^6).

Đầu ra

Một số nguyên duy nhất là tổng các giá trị φ(i) với 1 ≤ i ≤ 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.