This is the hard version of the problem. The only difference between the two versions is that in this version, you can make at most (\mathbf{7}) queries . This is an interactive problem. If you are unsure how interactive problems work, then it is recommended to read the guide for participants . We have a secret ruler that is missing one number (x) ((2 \leq x \leq 999)). When you measure an object of length (y), the ruler reports the following values: If (y < x), the ruler (correctly) measures the object as having length (y). If (y \geq x), the ruler incorrectly measures the object as having length (y+1). The ruler above is missing the number (4), so it correctly measures the first segment as length (3) but incorrectly measures the second segment as length (6) even though it is actually (5). You need to find the value of (x). To do that, you can make queries of the following form: (?~a~b) — in response, we will measure the side lengths of an (a \times b) rectangle with our ruler and multiply the results, reporting the measured area of the rectangle back to you. For example, if (x=4) and you query a (3 \times 5) rectangle, we will measure its side lengths as (3 \times 6) and report (18) back to you. Find the value of (x). You can ask at most (\mathbf{7}) queries. Each test contains multiple test cases. The first line of input contains a single integer (t) ((1 \leq t \leq 1000)) — the number of test cases. There is no initial input for each test case. You should begin the interaction by asking a query. To make a query, output a single line of the form (?~a~b) ((1 \leq a, b \leq 1000)). In response, you will be told the measured area of the rectangle, according to our secret ruler. When you are ready to print the answer, output a single line of the form (!~x) ((2 \leq x \leq 999)). After that, proceed to process the next test c