这是一个交互式问题。

有一个包含 $n$ 个单元格的数组，编号从 $1$ 到 $n$。对于每一对整数 $(i, j)$，其中 $1 \le i \le j \le n$，存在一个覆盖从 $i$ 到 $j$（包含 $i$ 和 $j$）所有单元格的屏障。每个屏障要么是激活的，要么是不激活的。如果一个单元格没有被任何激活的屏障覆盖，则它是可见的。否则，它是不可见的。

每个屏障的状态对你来说是未知的。你唯一能观察到的是可见单元格的数量。但是，你可以翻转任何屏障的状态：如果它是激活的，它会变为不激活，反之亦然。你的任务是使所有屏障变为不激活，从而使所有单元格都变得可见。

交互协议

首先，读取一个整数 $n$，表示单元格的数量 ($1 \le n \le 10$)。

接下来的交互将按轮次进行。你的程序应在每一轮开始时读取一个整数 $k$，表示当前可见单元格的数量 ($0 \le k \le n$)。

• 如果 $k = n$，则任务完成，你的程序必须退出。
• 如果 $k < n$，你可以翻转任何屏障的状态。在单独的一行中，打印两个整数 $i$ 和 $j$，以翻转 $(i, j)$ 屏障的状态 ($1 \le i \le j \le n$)。在你的查询之后，下一轮开始，你的程序应读取一个新的 $k$ 值。

你的解决方案必须在最多 $2500$ 次翻转内使所有单元格可见。在开始时，并非所有单元格都是可见的（第一轮中 $k < n$）。

交互器不是自适应的：在每个测试中，所有屏障的状态在程序执行前就已经确定。

样例

输入格式 1

3
0
0
1
2
3

输出格式 1

2 2
2 3
1 2
2 2

说明

在样例中，最初只有两个屏障 $(1, 2)$ 和 $(2, 3)$ 是激活的。这两个屏障覆盖了所有三个单元格，因此在第一轮中 $k = 0$。

• 翻转 $(2, 2)$ 屏障后，现在有三个激活的屏障，可见单元格数量仍然为 $k = 0$。
• 翻转 $(1, 2)$ 屏障后，单元格 $1$ 变得可见，因此现在有 $k = 1$ 个可见单元格。
• 翻转 $(2, 3)$ 屏障后，单元格 $3$ 也变得可见。现在唯一不可见的单元格是 $2$，它被唯一的激活屏障 $(2, 2)$ 覆盖，此时有 $k = 2$ 个可见单元格。
• 翻转 $(2, 2)$ 屏障后，所有屏障现在都不激活，所有单元格都变得可见。在读取 $k = 3$ 后，程序终止。