Tổng lớn nhất

Cho một số nguyên dương \(n\) \((n \ge 3)\).

Với mỗi số nguyên dương \(m\) thỏa mãn \(1 \le m \le n-1\), xét giá trị
$
GCD(m,n) + m
$
trong đó \(GCD(m,n)\) là ước chung lớn nhất của \(m\) và \(n\).

Yêu cầu:
Hãy tìm số \(m\) sao cho giá trị trên là lớn nhất.
Nếu có nhiều giá trị \(m\) thỏa mãn, hãy in ra giá trị \(m\) lớn nhất.

Input

Một dòng chứa số nguyên dương \(n\) \((3 \le n \le 10^{14})\).

Output

In ra một số nguyên dương là giá trị \(m\) tìm được.

Scoring

• Có \(30\%\) số điểm ứng với \(n \le 10^3\).
• Có \(30\%\) số điểm ứng với \(n \le 10^6\).
• \(40\%\) số điểm còn lại ứng với \(n \le 10^{14}\).

Sample Input 1

15

Sample Output 1

14