Interactive Guessing Game with Limited Queries

This is an interactive problem where one player (Yuan) secretly chooses a non-negative integer \(m\) such that \(0 \le m \le 10^{17}\). The other player (Yan) is allowed to ask queries of the form "? x" where \(x\) is a positive integer (with \(1 \le x \le 4 \times 10^8\)) and the reply is \(m \bmod x\). Note that Yuan does not change \(m\) during the game. Yan is allowed at most 2 queries to determine \(m\) for each game.

Formal description: There is a hidden integer \(m \in [0,10^{17}]\). For each query with a positive integer \(x\), the response is \(m \bmod x\). Using at most 2 queries, determine \(m\). There are \(T\) independent games. The interactive protocol is non-adaptive, meaning the hidden integer is fixed prior to any queries.

Note for implementation: In a true interactive setting you would output a query in the format "? x" and flush the output, then read the reply, and finally print the answer in the format "! m". However, for the purpose of this offline simulation, the hidden number \(m\) is provided as input for each game. Thus, your program should simply read and output \(m\) for each test case.

inputFormat

The first line of input contains a positive integer \(T\) which is the number of games. For each game, a single line follows containing the secret number \(m\) (where \(0 \le m \le 10^{17}\)). In a real interactive problem you would not be given \(m\) directly but would obtain remainders via queries.

outputFormat

For each game, output the guessed number \(m\) on a separate line.

sample

1
0

0