This is an interactive problem.

Lele and Xiaonuo have a "Piggy Car," and the license plate number of the Piggy Car is Pig Axxxx.

You want to guess the number xxxx ($0 \le x \le 9$ for each digit). Each time, you can query a four-digit number, and Xiaonuo will tell you how many digits in your query match the answer (a match is counted only if both the position and the digit are the same). Please guess the number within 12 queries.

Interaction

First, you need to read a positive integer $T$ ($T \le 1500$), representing the number of test cases. Then, proceed to play $T$ rounds of the number-guessing game.

To make a query, output a line in the format ? x, where $x$ is a four-digit number that may contain leading zeros. After flushing the output buffer, you need to read an integer between $0$ and $4$, representing how many digits in your query match the answer.

To guess the answer, output a line in the format ! x, where $x$ is a four-digit number that may contain leading zeros. After flushing the output buffer, your program should immediately start the next round of the game. If the current round is the last one, your program should exit immediately. Note that the final guess does not count as a query. That is, you can perform 12 queries and 1 guess.

The answer for each test case is predetermined. In other words, the judge is not adaptive.

You can flush the output buffer using the following methods:

• In C and C++, use fflush(stdout) (if using printf) or cout.flush() (if using cout).
• In Java and Kotlin, use System.out.flush().
• In Python, use stdout.flush().

Examples

Input 1

1
2
4

Output 1

? 1234
? 1314
! 1314