This is an interactive problem.

Tài and his brother really takes play the number-making game. Firstly, they will pick a prime number ~n~. Then they both prepare ~n~ blank pieces of paper and arrange them horizontally. The papers are numbered ~1~ to ~n~ from right to left.

The game goes as follow. Two brothers will take turns, with Tài going first. On their turn, the player will pick a blank piece of paper that hasn't been written on, then write a single digit from ~0~ to ~9~ of their choice. The game ends when all of the papers have been written on.

Tài is learning algebra, and is much interested in divisibility of numbers. Therefore Tài wants that after the game ends, the number obtained by reading the digits on the papers from left to right will be divisible by ~n~. Tài's brother on the other hand, wanting to add some friendly competitiveness to be game, will actively try to make the resulting number not divisible by ~n~.

Given the number ~n~ that the brothers picked, help Tài win the game by creating a number divisible by ~n~. Note that it is allowed that the resulting number may have leading zeroes.

Interaction

In this problem, you will play as Tài, and the jury will play as his brother.

The jury program will first print a single integer ~t~ (~1 \le t \le 10~), the number of game matches. Each match will happen as follow.

The jury program first prints a single integer ~n~ (~1 \le n \le 100\,000~, ~n~ is a prime number), the integer that the brothers picked.

Then you and the jury program will, ~n~ times in total, take turns printing two integers ~p~ and ~d~ (~1 \le p \le n~, ~0 \le d \le 9~), denoting on their respective turn, the player chooses to fill in the digit ~d~ into the paper indexed ~p~ from right to left.

After making ~n~ turns in total, the jury outputs a single integer ~x~ denoting the result. If the number created is indeed divisible by ~n~, the jury program outputs ~x = 1~. Afterwards you can proceed with the next match (if any). If the number created is not divisible by ~n~, the jury program outputs ~x = 0~, and will not provide you with additional inputs from that point onwards. In such case, your program must terminate to receive a Wrong answer verdict, otherwise it may receive arbitrary verdict.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Time Limit Exceeded. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Scoring

• Subtask 1 (~30~ points): ~n < 10~.

• Subtask 2 (~120~ points): No additional constraints

The total score for this problem is ~150~.

Sample 1

2
2

2 5
1
3

2 3

1
  

1 8



1 5

3 7

  

Notes

There are ~t = 2~ matches.

In the first match with ~n = 2~, Tài goes first and fills in the first paper from right to left with the digit ~8~. The digits are now:

Afterwards, the jury program chooses to fill in ~5~ to the remaining sheet. The digits are now:

The digits on the papers read ~58~, which is divisible by ~2~. Thereby the jury program outputs ~x = 1~ and begins the next match.

In the second match with ~n = 3~, Tài goes first and fills in the first paper from right to left with the digit ~5~. The digits are now:

Afterwards, the jury program chooses to fill in ~3~ to the second sheet from right to left. The digits are now:

Finally, Tài chooses the digit ~7~ to fill in the final sheet. The digits are now:

The row of paper reads ~735~, which is ~3~ so the jury outputs ~x = 1~ and terminates. Tài emerges victorious for all the matches.