Chia nhỏ số nguyên

Với mỗi số nguyên \(x \ge 2\), ký hiệu \(f(x)\) là ước lớn nhất của \(x\) nhỏ hơn \(x\) (ví dụ \(f(12) = 6\), \(f(7) = 1\), \(f(9) = 3\)).

Cho số nguyên \(N\). Ta muốn tách \(N\) thành tổng của một hay nhiều số nguyên, mỗi số không nhỏ hơn 2:

Chi phí của một cách tách là \(f(k_1) + f(k_2) + \dots + f(k_m)\). Cách tách chỉ gồm một số (\(m = 1\), \(k_1 = N\)) cũng hợp lệ.

Hãy tính chi phí nhỏ nhất có thể đạt được.

Input

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

Output

In ra chi phí nhỏ nhất.

Constraints

• \(2 \le N < 10^9\)

Sample Input

27

Sample Output

3

Explanation

Có thể tách \(27 = 7 + 7 + 13\), cả ba số đều là số nguyên tố nên mỗi số có chi phí \(1\), tổng chi phí là \(3\). Không có cách tách nào cho tổng chi phí nhỏ hơn.