Problem G
Guessing Primes

Victory!

Your friends are all on board with the hype of a popular game, where you need to guess a five-letter word in six tries. Unfortunately, your language skills are not the greatest, so this game is not really your cup of tea. However, your mathematics skills greatly outmatch your friends’, so you start playing a game called “Brave Alternative Primes Challenge”¹ instead. In order to show off your skills to your friends, you decide to write a program that will always beat the game.

In this game, you need to guess a secret prime number of five digits (i.e., between $10^4$ and $10^5$) in six turns. After guessing a prime number, you will receive a response consisting of five characters, each corresponding to a single digit in your guess:

• “g” (green) means you guessed the corresponding digit correctly;

• “y” (yellow) means that the digit is present in a position that is not yet green, but not at this position;

• “w” (white) means that this digit is neither green nor yellow.

Note that the interactor colours at most one of your guessed digits per digit in the secret answer. If your guess includes more occurrences of a digit than the answer, only some of them will be green or yellow.

You win the game when the response is green for all five digits.

Interaction

This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:

The interactor first sends one line with an integer $n$ ($1 \leq n \leq 1000$), the number of rounds.

Then, for each of the $n$ rounds, your program should make at most $6$ guesses, each guess being a prime number of five digits (i.e., between $10^4$ and $10^5$). The interactor will respond with a string of characters in “wyg”, as described above. A round ends when the response is “ggggg”.

The interactor is not adaptive, i.e., the secret prime number is fixed during a round.

Make sure you flush the buffer after each write.

A testing tool is provided to help you develop your solution.

Using more than $6$ queries in one round will result in a wrong answer.

2

54323

ywyww

98737

wwwyg

31583

gggww

31517

ggggg

99991

wwwwy

44449

wgwgw

14143

ggggg