Trò chơi số nguyên tố

Alice và Bob chơi một trò chơi. Họ chọn một số nguyên khởi đầu $X_0\ge 3$ rồi lần lượt thực hiện các lượt đi, Alice đi trước.

Ở lượt thứ $i$, người đến lượt chọn một số nguyên tố $p<X_{i-1}$ rồi công bố $X_i$ là bội nhỏ nhất của $p$ mà không nhỏ hơn $X_{i-1}$. Nói cách khác, người chơi chọn số nguyên tố $p<X_{i-1}$ và tính $X_i$ nhỏ nhất sao cho $X_i\ge X_{i-1}$ và $p$ chia hết $X_i$. Lưu ý nếu $p$ đã chia hết $X_{i-1}$ thì $X_i=X_{i-1}$.

Eve chỉ quan sát được trạng thái trò chơi sau đúng hai lượt đi, tức giá trị $X_2$. Cho $X_2$, hãy giúp Eve tìm giá trị $X_0$ nhỏ nhất có thể. Hai người chơi không nhất thiết chơi tối ưu, nên cần xét mọi diễn biến hợp lệ của trò chơi.

Dữ liệu vào

Một số nguyên duy nhất $X_2$. Bảo đảm $X_2$ là hợp số (không phải số nguyên tố).

Dữ liệu ra

Một số nguyên duy nhất, là giá trị $X_0$ nhỏ nhất có thể.

Ràng buộc

• $4\le X_2\le {10}^6$
• $X_2$ là hợp số.

Ví dụ