这是一个交互式问题！

存在一个由 $N$ 个互不相同的正整数组成的隐藏数组 $a_1, a_2, \dots, a_N$（其中 $N$ 为奇数）；该数组的一个错误副本存储在另一个隐藏数组 $b$ 中。数组 $b$ 的每个元素定义如下：

• $b_1 = a_2$
• $b_N = a_{N-1}$
• 对于每个满足 $1 < i < N$ 的 $i$，$b_i = a_{i-1}$ 或 $b_i = a_{i+1}$（即相邻元素之一）

你需要确定是否存在两个下标 $i$ 和 $j$（$i \neq j$，$1 \le i, j \le N$）使得 $b_i = b_j$。如果存在这样的下标，请返回它们；否则，指出不存在这样的下标。

你可以通过以下操作查询数组 $a$ 和 $b$ 的元素：

• 1 i：返回 $a_i$ 的值（$1 \le a_i \le 10^9$）
• 2 i：返回 $b_i$ 的值（$1 \le b_i \le 10^9$）

你最多可以进行 20 次查询。

交互

首先，你必须读取一行，包含一个整数 $T$（$1 \le T \le 100$），表示测试用例的数量。

接下来是 $T$ 个测试用例的交互过程。

对于每个测试用例，你必须首先读取一行，包含一个整数 $N$（$3 \le N \le 2\,001$，$N$ 为奇数）。

然后交互开始。你可以输出一行，包含以下内容之一：

• 1 x（询问 $a_x$）：然后，读取一行，包含一个整数 $a_x$。
• 2 x（询问 $b_x$）：然后，读取一行，包含一个整数 $b_x$。
• 3 i j（回答：两个下标 $i, j$，满足 $b_i = b_j$；如果不存在这样的两个下标，则输出 -1 -1）：然后，如果有下一个测试用例，则继续进行；否则，程序终止。

在输出每一行后，请不要忘记清空输出缓冲区（flush）。例如：

• C/C++ 中的 fflush(stdout)；
• Java 中的 System.out.flush()；
• Python 中的 sys.stdout.flush()；
• Pascal 中的 flush(output)；
• 其他语言请参阅相应文档。

样例

输入样例 1

1
7
2
2

输出样例 1

2 3
2 1
3 1 3