Cho một số nguyên dương \(n\) với \(n \geq 3\). Tìm số nguyên dương \(m < n - 1\) thoả mãn rằng tổng \(\gcd(m,n) + m\) đạt giá trị lớn nhất. Trong đó, \(\gcd(m,n)\) là ước chung lớn nhất của hai số \(m,n\).

Lưu ý: Nếu có nhiều hơn một số \(m\) thoả mãn điều kiện trên thì chỉ đưa ra số \(m\) có giá trị lớn nhất.

Input Specification

Gồm duy nhất số nguyên dương \(n\).

Output Specification

In ra số nguyên dương \(m\) tìm được trên một dòng duy nhất.

Constraints

• Subtask 1 (60%): \(n \leq 10^4\).
• Subtask 2 (40%): \(n \leq 10^{14}\).

Input Sample

15

Output Sample

12