Cho một số nguyên dương ~n~ (~n \ge 3~). Tìm số nguyên dương ~m~ (~1 \le m < n - 1~) để tổng ~GCD(m, n) + m~ đạt giá trị lớn nhất. Với ~GCD(m, n)~ là ước chung lớn nhất của 2 số ~m~ và ~n~. Nếu có nhiều số ~m~ thỏa mãn thì đưa ra số ~m~ lớn nhất.

Yêu cầu: Tìm số nguyên dương ~m~ thỏa mãn điều kiện trên.

Input

• Dòng duy nhất chứa số nguyên dương ~n~ (~n \le 10^{14}~).

Output

• Ghi ra số nguyên dương ~m~ tìm được.

Sample Input 1

15

Sample Output 1

12