Trong máy tính có 2 số \(N\) và \(C\). Bạn được cho biết trước số \(N\), nhưng số \(C\) bị giấu đi. Nhiệm vụ của bạn là đoán được số \(C\).

Để giúp bạn đoán được số \(C\), bạn được quyền giao tiếp với máy tính không quá \(64\) lần. Trong mỗi lần, bạn sẽ gửi cho máy tính một số nguyên từ \(1\) đến \(N\); tuy nhiên bạn không thể gửi cùng một số trong hai lượt khác nhau. Sau mỗi lần bạn gửi con số, hệ thống sẽ trả về một trong hai xâu \(YES\) hoặc \(NO\). Ở lượt đầu tiên, máy tính sẽ gửi ngẫu nhiên cho bạn một trong hai xâu này. Kể từ lượt thứ 2 trở đi, máy sẽ trả về \(YES\) khi và chỉ khi chênh lệch của số được gửi lần này và số được gửi ở lần ngay trước đó không bé hơn \(C\), và \(NO\) nếu ngược lại. Cụ thể, nếu bạn gửi số \(X\) trong lần thứ \(i - 1\) và số \(Y\) trong lần thứ \(i\), bạn sẽ nhận về \(YES\) ở lượt thứ \(i\) khi và chỉ khi \(|X - Y| \geq C\) và sẽ nhận về \(NO\) nếu \(|X - Y| < C\).

Trong nhiệm vụ này, mỗi test \(T\) thử nghiệm riêng biệt, để qua được một test bạn phải đoán đúng giá trị \(C\) trong các thử nghiệm đó.

Tương tác

Đây là bài toán tương tác. Mỗi test gồm \(T\) test con.

• Đầu tiên, bạn cần đọc vào giá trị \(T\).
• \(T\) test sẽ được thực hiện tuần tự, trong đó ở mỗi test:
• Bạn đọc vào số nguyên \(N\)
• Truy vấn ? X: chương trình sẽ trả lời YES nếu chênh lệnh giữa hai phần tử trong 2 lần gửi gần nhất lớn hơn hoặc bằng C và NO trong trường hợp ngược lại. Các giá trị của \(X\) trong các lần gọi hàm phải đôi một phân biệt, nếu không, bạn sẽ nhận được kết quả Wrong Answer. Trong mỗi test con, bạn được hỏi truy vấn này không quá \(64\) lần.
• Trả lời = C: đưa ra giá trị \(C\) cần tìm. Bạn chỉ được trả lời một lần với mỗi test con.

Constants

\(1 \leq C \leq N \leq 10^{18}, 1 \leq T \leq 1000\)

Subtask

• Subtask 1 (9 điểm): \(N \leq 64\)
• Subtask 2 (13 điểm): \(N \leq 125\)
• Subtask 3 (21 điểm): \(N \leq 1000\)`
• Subtask 4 (24 điểm): \(N \leq 10^9\)
• Subtask 5 (33 điểm): \(N \leq 10^{18}\)

Ví dụ