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}\).