Số bí mật của Snape

Thầy Snape đã chọn một số nguyên bí mật $x$ trong khoảng từ $1$ đến $n$.

Mục tiêu của bạn là xác định chính xác giá trị của $x$.

Giao thức tương tác

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

? y

trong đó $1\le y\le n$. Thầy Snape 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

Giới hạn câu hỏi: Bạn được hỏi tối đa $25$ câu hỏi.

Tối đa một lời nói dối: Thầy Snape được phép nói dối nhiều nhất một lần. Cụ thể:

• Đúng một câu trả lời có thể sai
• Tất cả các câu trả lời còn lại đều đúng với $x$ đã chọn

Thầy Snape biến hóa: Thầy Snape không cố định $x$ từ đầu. Sau mỗi câu hỏi, Thầy Snape có thể thay đổi $x$, miễn là:

• Tất cả các câu trả lời trước đó (trừ tối đa một lời nói dối) vẫn nhất quán với $x$ mới

Nhiệm vụ

Sau khi hỏi xong, in ra câu trả lời cuối cùng:

! x

Câu trả lời này không tính vào giới hạn câu hỏi.

Quan trọng: Vì Thầy Snape thích biến hoá, 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 các câu trả lời (cho phép tối đa 1 câu trả lời sai). Nếu còn nhiều hơn một giá trị khả thi, Thầy Snape 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 một số nguyên $n$.

Dữ liệu ra

Để hỏi: ? y

Để trả lời: ! x

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

Ràng buộc

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

Ví dụ

Ghi chú

Trong ví dụ trên, Thầy Snape đã nói dối 1 lần ở câu hỏi ? 5. Thực tế $x=4$ không chia hết cho 5, nhưng Thầy Snape trả lời YES.

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