Trong buổi học toán rời rạc, cô giáo yêu cầu Tèo tìm căn nguyên thủy (primitive root) nhỏ nhất modulo \(p\), với \(p\) là số nguyên tố. Căn nguyên thủy \(g\) là số có bậc bằng \(p-1\), nghĩa là các lũy thừa \(g^0, g^1, \dots, g^{p-2}\) sinh ra toàn bộ tập \(\{1, 2, \dots, p-1\}\).

Định dạng đầu vào

• Một dòng chứa số nguyên tố \(p\) (\(2 \le p \le 10^9\)).

Định dạng đầu ra

• Căn nguyên thủy nhỏ nhất modulo \(p\).

Ví dụ

Input:

7

Output:

3

Giải thích: \(3^1=3, 3^2=2, 3^3=6, 3^4=4, 3^5=5, 3^6=1 \pmod{7}\). Bậc của 3 là 6 = p-1.

Ràng buộc

• 100% số điểm: \(p \le 10^9\).