B. Easy Composite
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob has a secret prime number $$$p$$$ ($$$10 \le p \le 10^8$$$). While he appreciates the properties of prime numbers, he would prefer it if his number were composite.

To achieve this, Bob can modify $$$p$$$ by prepending one or more decimal digits to the front of its decimal representation. He wants to prepend the minimum number of digits necessary to transform $$$p$$$ into a composite number.

For example, if $$$p = 11$$$:

  • Prepending $$$5$$$ gives $$$511$$$, which is a composite number ($$$7 \times 73$$$).
  • Prepending $$$12$$$ gives $$$1211$$$, which is also a composite number ($$$7 \times 173$$$).
In this case, $$$12$$$ is not an optimal choice because it prepends two digits, whereas prepending the single digit $$$5$$$ already results in a composite number.

Bob asks for your help.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^5$$$) — the number of test cases.

Interaction

This is an interactive problem. Your program should perform the following steps for each test case:

  1. First, output an integer $$$x$$$ ($$$1 \le x \le 10^6$$$) that you wish to test as a prefix.
  2. Remember to flush your standard output after printing $$$x$$$.
  3. The judge will respond with YES if the number formed by prepending $$$x$$$ to $$$p$$$ is composite, or NO if it is prime.
  4. Finally, output an integer $$$y$$$ ($$$1 \le y \le 10^6$$$) such that prepending $$$y$$$ to $$$p$$$ results in a composite number using the minimum number of digits possible. If multiple such values of $$$y$$$ exist, you may output any of them.
  5. Flush your output again after printing $$$y$$$.
Example
Input
1

NO
Output

2

5
Note

In the sample interaction, there is only one test case ($$$T = 1$$$). The hidden prime number is $$$p = 11$$$, which is known only to the judge. The value of $$$p$$$ remains constant throughout a single test case, though it may vary across different test cases. The interactor is not adaptive; that is, the hidden prime $$$p$$$ is fixed before the interaction begins and does not change based on your outputs.

The sample interaction proceeds as follows:

  • The judge begins by outputting $$$1$$$ (the value of $$$T$$$), which the solution program reads from standard input.
  • The solution outputs $$$2$$$ as a test prefix. The judge evaluates the number $$$211$$$. Since $$$211$$$ is not a composite number, the judge outputs NO.
  • Finally, the solution outputs $$$5$$$. This is a correct answer because $$$511$$$ ($$$7 \times 73$$$) is a composite number formed by prepending a single digit to $$$p = 11$$$.
  • Note that the solution could have also correctly output any of $$$\{1,\; 4,\; 6,\; 7\}$$$ for the final answer, as the numbers $$$111,\; 411,\; 611$$$ and $$$711$$$ are all composite and each requires prepending only a single digit to $$$p=11$$$.

After outputting each line, you must flush the output. For example:

  • fflush(stdout); in C/C++
  • System.out.flush(); in Java
  • sys.stdout.flush() in Python