Định nghĩa dãy \(a\) gồm \(n\) phần tử là dãy đẹp khi:

• Ước chung lớn nhất của mọi cặp \((a_i, a_j)\) bằng 1 với mọi \(i \ne j\), và
• \(a_i > 1\) với mọi \(i\).

Cho số \(n\), tìm tổng nhỏ nhất của dãy đẹp có \(n\) phần tử.

Dữ liệu vào

• Một số nguyên duy nhất \(n\ (1 \leq n \leq 10^6)\): độ dài của dãy đẹp cần tìm.

Dữ liệu ra

• Một số nguyên duy nhất là tổng nhỏ nhất của dãy đẹp tìm được.

Scoring

• Subtask 1 (10%): \(n \leq 10\)
• Subtask 2 (30%): \(n \leq 10^3\)
• Subtask 3 (60%): \(n \leq 10^6\)

Input

1

Output

2