D. Interactive lock
time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

Interactive combination locks are quite popular nowadays. One of such locks is used in order to test the staff members of an office. They are trying to unlock it but so far there is no success.

Lock consists of T integer-valued sections and you have to guess the divisor (not equal to 1) for each of them (102 ≤ Xi ≤ 104) in the following way:

  • You pick any positive integer number (candidate divisor);
  • if X is divisible by your number, you will receive «YES» message and proceed to guessing the next section;
  • if not, you will receive «NO», your number will be subtracted from X and you will now need to guess the divisor of the changed number.

The number being guessed must stay positive after subtraction and your are not allowed to use the same divisor for the same section more than once. In case all the conditions are met and each section is completed the door will be opened.

The staff has been struggling with this task for the whole day. Now people need a hero that will open the door for them. Are you worthy?

Input

First line has number T — the amount of lock sections (1 ≤ T ≤ 500).

Then you will have to read the answers to guess attempts in the form of «YES» or «NO» messages. They will arrive after each guess attempt.

Don’t forget to put a newline character and to flush the output stream (flush(stdout) in C++, System.out.flush() in Java and flush(output) in Pascal) after you print your query.

In case of interactor communication protocol violation you program will be closed automatically.

Output

Output candidate divisors. There may be more than one such attempt depending on the success of previous attempts.

Examples
Input
3

YES

NO

YES

YES
Output
2

2

3

2
Note

In the sample test given example work correctly for the lock, consisting of three sections with numbers 100, 101 and 102.