这是一个交互式问题。

生成 $n-1$ 个长度为 50 的随机二进制字符串 $s_i$。然后，其中一个字符串被复制，并将所有 $n$ 个字符串打乱顺序。你需要找到相等字符串的下标。

你最多可以进行 25 000 次查询。每次查询是一个下标对 $(i, j)$。查询的回答是 $s_i$ 和 $s_j$ 之间的汉明距离——即它们在不同位置上的数量。

保证所有字符串都是从均匀分布中随机选取的。此外，每个测试用例的字符串列表是固定的——交互器不是自适应的。

交互

首先，交互器打印一个整数 $n$ ($2 \le n \le 1000$)，表示字符串的总数。

然后，你可以进行最多 25 000 次查询，格式为 “i j” ($1 \le i, j \le n, i \neq j$)。请记住在每次查询后刷新输出！

对于每次查询，你将收到一个整数 $d$ ($0 \le d \le 50$)，表示 $s_i$ 和 $s_j$ 之间的汉明距离。在收到 $d = 0$ 后，你的程序应该终止。

样例

输入 1

4
21
23
21
0

输出 1

1 2
2 3
1 4
2 4

说明

样例中的字符串：

• 10110000010010010101011100011000000011001011000101
• 10101101000111001111100000010010000100101011100101
• 10011110110010011111100111011000010100011101111011
• 10101101000111001111100000010010000100101011100101