Số bí mật của Hagrid

Thầy Hagrid đã 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

trong đó $1\le y\le n$. Thầy Hagrid sẽ trả lời:

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

Quy tắc đặc biệt

Thầy Hagrid biến hóa: Thầy Hagrid không cố định $x$ từ đầu. Sau mỗi câu hỏi, Thầy Hagrid có thể thay đổi $x$, miễn là tất cả các câu trả lời trước đó vẫn nhất quán với $x$ mới.

Thầy Hagrid luôn nói thật: Tất cả câu trả lời đều chính xác với $x$ hiện tại.

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

! x

Quan trọng: Vì Thầy Hagrid biến hóa, bạn phải đảm bảo rằng sau tất cả các câu hỏi, chỉ còn duy nhất một giá trị $x$ thỏa mãn tất cả câu trả lời. Nếu còn nhiều hơn một giá trị khả thi, Thầy Hagrid sẽ chọn giá trị khác với câu trả lời của bạn.

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 100$
• Bạn được hỏi tối đa $25$ câu hỏi

Ví dụ

Ghi chú

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

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