Interactive Guessing Game: Flame and Circle

Flame and Circle are playing a game. Flame secretly chooses a positive integer \(m\) such that \(2 \le m \le 10^{17}\) and Circle has to guess the value of \(m\) by asking queries. However, Flame is fair and will not change the number throughout the game.

You are allowed to ask queries of the following form. For any non-negative integer \(x\) (with \(0 \le x \le 10^{18}\)), you may ask:

? x

The response will be the value of \(x \bmod m\). Your goal is to determine \(m\) using at most 2 queries per test case.

After you have identified \(m\), you must output the final answer in the following format:

! m

Important: This is an interactive problem with a non-adaptive judge. In the actual interaction, once you issue a query, you must flush the output to ensure your query is sent. For the purpose of this problem (and to pass all test cases), the hidden number \(m\) is provided in the input, so you can simulate the interactive process offline.

The formal description:

• There is a hidden integer \(m\) with \(2 \le m \le 10^{17}\).
• You can make a query by printing ? x for any non-negative integer \(x\) (with \(0 \le x \le 10^{18}\)), and you will receive \(x \bmod m\) in response.
• After at most 2 queries, print ! m to output your guess.
• This game is played for \(T\) test cases. In each test case, the hidden number \(m\) remains fixed and does not change in response to your queries.

Note: In our offline simulation the input will contain the value of \(m\) for each test case, so you may simply output \(m\) as your answer.

inputFormat

The input consists of multiple test cases. The first line contains a single integer \(T\) representing the number of test cases. For each test case, a line is given containing the hidden integer \(m\) \( (2 \le m \le 10^{17}) \).

Note: In a real interactive environment you would need to use queries to determine \(m\), but here \(m\) is directly provided in the input.

outputFormat

For each test case, output a single line in the format ! m where \(m\) is the guessed number. The output must exactly match the hidden number for each test case.

sample

1
2

! 2

</p>