You, a wizard whose creation was destroyed by a dragon, are determined to hunt it down with a magical AOE tracker. But it seems to be toyed with... This is an interactive problem. There is a hidden binary array (a) of length (n) ((\mathbf{n}) is a power of 2 ) and a hidden integer (k\ (2 \le k \le n - 1)). The array (a) contains exactly one 1 (and all other elements are 0). For two integers (l) and (r) ((1 \le l \le r \le n)), define the range sum (s(l, r) = a_l + a_{l+1} + \cdots + a_r). You have a magical device that takes ranges and returns range sums, but it returns the opposite result when the range has length at least (k). Formally, in one query, you can give it a pair of integers (l, r) where (1 \le l \le r \le n), and it will return either (0) or (1) according to the following rules: If (r - l + 1 < k), it will return (s(l, r)). If (r - l + 1 \ge k), it will return (1 - s(l, r)). Find (k) using at most (33) queries. The device is not adaptive. It means that the hidden (a) and (k) are fixed before the interaction and will not change during the interaction. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 500)). The description of the test cases follows. The first line of each test case contains one positive integer (n) ((4 \le n \le 2^{30})) — the length of the hidden array. It is guaranteed that (\mathbf{n}) is a power of 2 ; that is, (n = 2^m) for some non-negative integer (m). You can make queries in the following way — print one line of the form "(\mathtt{?}\,l\,r)" where (1 \le l \le r \le n). After that, read a single integer: (0) or (1), as described in the statement. If you want to print the answer (k), output "(\mathtt{!}\,k)". Then, the interaction continues with the next test case. Printing the answer does not count towards the number of quer