To read the problem statement in English, choose the language using the flag on the navigation bar.

Đây là một bài toán interactive.

Tài và anh trai rất thích chơi trò chơi tạo số. Đầu tiên hai anh em sẽ chọn ra một số nguyên tố ~n~. Sau đó cả hai sẽ chuẩn bị ra ~n~ mảnh giấy và xếp chúng ngay ngắn theo một hàng ngang. Các tờ giấy được đánh số từ ~1~ đến ~n~ từ phải qua trái.

Trò chơi sẽ diễn ra như sau. Hai anh em sẽ luân phiên chơi, với Tài là người đi trước. Người chơi khi đến lượt đi của mình sẽ chọn ra một mảnh giấy chưa được viết lên, và viết lên đó một chữ số từ ~0~ đến ~9~ theo ý của mình. Trò chơi sẽ kết thúc khi tất cả các mảnh giấy đã được viết lên.

Tài đang học đến số học, và rất thích sự chia hết. Vì vậy Tài muốn rằng sau khi trò chơi kết thúc, con số thu được khi đọc các mảnh giấy từ trái qua phải sẽ là một số chia hết cho ~n~. Tất nhiên để trò chơi thêm phần vui vẻ, mang tính chất đối kháng, anh của Tài sẽ cố gắng điền các số sao cho số được tạo ra sẽ không chia hết cho ~n~.

Cho biết số ~n~ mà hai anh em đã chọn, hãy giúp Tài chiến thắng trò chơi này bằng cách tạo ra một số chia hết cho ~n~. Lưu ý rằng số tạo thành sau khi trò chơi kết thúc có thể bắt đầu bằng chữ số 0.

Interaction

Trong bài toán này bạn sẽ chơi trò chơi với vai Tài và chương trình của ban tổ chức sẽ chơi với vai của anh trai Tài.

Đầu tiên chương trình của ban tổ chức sẽ in ra một số ~t~ (~1 \le t \le 10~) là số trận hai anh em sẽ chơi. Mỗi trận chơi sẽ được diễn ra như sau.

Đầu tiên chương trình của ban tổ chức sẽ in ra một số ~n~ (~1 \le n \le 100\,000~, ~n~ là số nguyên tố) là số mà hai anh em đã cùng chọn với nhau.

Tiếp đó bạn cùng chương trình của ban tổ chức sẽ thực hiện ~n~ lần luân phiên nhau in ra hai số nguyên ~p~ và ~d~ (~1 \le p \le n~, ~0 \le d \le 9~) thể hiện người chơi khi đến lượt sẽ điền chữ số ~d~ vào mảnh giấy thứ ~p~ từ phải sang trái.

Sau ~n~ lần cùng nhau tương tác, chương trình của ban tổ chức sẽ in ra một số ~x~. Trong trường hợp số được tạo ra là số chia hết cho ~n~, ban tổ chức sẽ in ra ~x = 1~. Khi đó bạn có thể tiếp tục thao tác với trận tiếp theo (nếu có). Trường hợp mà số được tạo thành không chia hết cho ~n~, chương trình của ban tổ chức sẽ in ra ~x = 0~ và không in thêm dữ liệu nào nữa. Trong trường hợp này, bạn cần dừng chương trình của mình để nhận được verdict Wrong answer (đáp án sai), nếu không bạn sẽ nhận được kết quả bất kì.

Sau mỗi một lần in đáp án, hãy nhớ flush đầu ra chuẩn, nếu không bạn có thể nhận verdict Time Limit Exceeded. Để làm điều này, bạn có thể sử dụng:

• fflush(stdout) hoặc cout.flush() trong C++;
• System.out.flush() trong Java;
• flush(output) trong Pascal;
• stdout.flush() trong Python;
• xem tài liệu chuẩn đối với các ngôn ngữ khác.

Scoring

• Subtask 1, tương ứng với ~30~ điểm, có ~n < 10~.

• Subtask 2, tương ứng với ~120~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán có ~150~ điểm.

Sample 1

2
2

2 5
1
3

2 3

1
  

1 8



1 5

3 7

  

Notes

Ở ví dụ trên có ~t = 2~ trận.

Ở trận đầu tiên có ~n = 2~, Tài đi trước và chọn điền vào mảnh giấy thứ nhất từ phải sang trái chữ số ~8~. Chữ số trên các mảnh giấy lúc này là:

Sau đó, chương trình của ban tổ chức chọn điền chữ số ~5~ vào mảnh giấy thứ hai từ phải sang trái. Chữ số trên các mảnh giấy lúc này là:

Số tạo ra khi đọc các mảnh giấy là ~58~, đây là một số chia hết cho ~2~ nên chương trình của ban tổ chức sẽ in ra ~x = 1~ và bắt đầu trận tiếp theo.

Ở trận thứ hai có ~n = 3~, Tài đi trước và chọn điền vào mảnh giấy thứ nhất từ phải sang trái chữ số ~5~. Chữ số trên các mảnh giấy lúc này là:

Sau đó, chương trình của ban tổ chức chọn điền chữ số ~3~ vào mảnh giấy thứ hai từ phải sang trái. Chữ số trên các mảnh giấy lúc này là:

Cuối cùng, Tài chọn điền chữ số ~7~ vào mảnh giấy thứ ba từ phải sang trái. Chữ số trên các mảnh giấy lúc này là:

Số tạo ra khi đọc các mảnh giấy là ~735~, đây là một số chia hết cho ~3~ nên chương trình của ban tổ chức sẽ in ra ~x = 1~ và kết thúc. Tài đã chiến thắng tất cả các trận.