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.
Interaction
This is an interactive problem. Your program should perform the following steps for each test case:
- First, output an integer $$$x$$$ ($$$1 \le x \le 10^6$$$) that you wish to test as a prefix.
- Remember to flush your standard output after printing $$$x$$$.
- The judge will respond with YES if the number formed by prepending $$$x$$$ to $$$p$$$ is composite, or NO if it is prime.
- 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.
- Flush your output again after printing $$$y$$$.
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