Định nghĩa: \(\gcd(m, n)\) là ước số chung lớn nhất của \(m\) và \(n\).

Cho số nguyên dương \(N\) (\(3 \le N \le 10^{12}\)).

Tìm số nguyên dương \(M\) (\(1 \le M \le N-2\)) để tổng \(\gcd(M, N) + M\) đạt giá trị lớn nhất. Nếu có nhiều số \(M\) thỏa mãn thì đưa ra số \(M\) lớn nhất.

Input

• Một số nguyên dương \(N\) (\(3 \le N \le 10^{12}\)).

Output

• In ra số nguyên dương \(M\) tìm được.

Example

15

12