Số bí mật của McGonagall

Cô McGonagall đã chọn một số nguyên bí mật $x$ trong khoảng từ $1$ đến $n$.

Bạn có thể đặt câu hỏi theo định dạng:

? y

Cô McGonagall sẽ trả lời:

• YES nếu $x$ chia hết cho $y$
• NO nếu ngược lại

Sau khi tìm ra đáp án, in ra:

! x

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$.

Dữ liệu ra

Để hỏi: ? y (với $1\le y\le n$)

Để trả lời: ! x

Sau mỗi truy vấn, bạn phải flush output.

Ràng buộc

• $1\le n\le 50$
• Bạn được hỏi tối đa $25$ câu hỏi

Ví dụ

Ghi chú

Trong ví dụ, $x=12$. Ta biết $x$ chia hết cho 2, 3, 4 nhưng không chia hết cho 5 và 8. Số duy nhất thỏa mãn trong [1, 50] là 12.

Tham khảo: Hướng dẫn giải bài tập Interactive