This is an interactive problem.

$$$n - 1$$$ random binary strings $$$s_i$$$ of length 50 are generated. Then, one of the strings is duplicated, and all $$$n$$$ strings are shuffled. You need to find indexes of equal strings.

You can ask at most $$$25\ 000$$$ queries. Each query is a pair $$$(i, j)$$$. The answer to the query is the Hamming distance between $$$s_i$$$ and $$$s_j$$$ — the number of positions where they differ.

It is guaranteed that all strings are picked randomly from the uniform distribution. Also, the list of strings is fixed for each test — interactor is not adaptive.

First, the interactor prints one integer $$$n$$$ ($$$2 \le n \le 1000$$$) — the total number of strings.

Then, you can ask at most $$$25\ 000$$$ queries in the format "i j" ($$$1 \le i, j \le n, i \ne j$$$). Don't forget to flush the output after each query!

For each query, you will receive one integer $$$d$$$ ($$$0 \le d \le 50$$$) — the Hamming distance between $$$s_i$$$ and $$$s_j$$$. After receiving $$$d=0$$$, your program should terminate.