Ước đầu tiên lớn hơn 1 (Smallest Divisor Greater Than One)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho số nguyên $n\ge2$. Tìm số nguyên dương nhỏ nhất $d>1$ sao cho $n$ chia hết cho $d$. Nếu $n$ là số nguyên tố, kết quả là chính $n$.

Input

Một số nguyên $n$.

Output

In ước nhỏ nhất lớn hơn 1 của $n$.

Subtask

• Subtask 1 (20%): $2\le n\le100$.
• Subtask 2 (30%): $2\le n\le10^5$.
• Subtask 3 (50%): $2\le n\le10^9$.

Ví dụ

Ví dụ 1

Input

21

Output

3

Giải thích

21 không chia hết cho 2 nhưng chia hết cho 3; in 3.

Ví dụ 2

Input

49

Output

7

Giải thích

Ước 7 là ước đầu tiên lớn hơn 1.

Ví dụ 3

Input

13

Output

13

Giải thích

Không có ước từ 2 đến căn bậc hai, nên 13 nguyên tố và chính là đáp án.