这是一个交互式问题。

你是国际象棋俱乐部的总教练。俱乐部有 $2n$ 名选手，每名选手都有一个可以用数字表示的实力值，且所有选手的实力值各不相同。你并不知道选手的实力值。

你需要选出 $n$ 名选手代表俱乐部参加即将到来的锦标赛。显然，你希望选出实力最强的 $n$ 名选手。

为了做到这一点，你可以组织选手之间的比赛。在每一场比赛中，你挑选两名选手，他们进行若干局对弈，你会得知其中哪一位的实力更强。你可以在决定下一场比赛的参赛选手之前，等待上一场比赛的结果。

然而，你并不想确切地知道这 $n$ 名选手之间的实力对比，因为那样会使锦标赛本身变得不那么引人入胜。更正式地说，你必须达到这样一种状态：在所有与你组织的比赛结果相符的情况中，选出实力最强的 $n$ 名选手的方案有且仅有一种，但在这 $n$ 名选手内部，与比赛结果相符的实力排序方式至少有两种。

交互

你的程序需要在一轮运行中处理多个测试用例。首先，读取整数 $t$ ($t \ge 1$)，表示测试用例的数量。然后，依次处理每个测试用例。

在每个测试用例中，程序首先读取整数 $n$ ($3 \le n \le 100$)，表示从 $2n$ 名选手中选出 $n$ 名。所有测试用例中 $n$ 的平方和不超过 $10\,000$。

之后，你的程序可以进行零次或多次比赛。要组织一场比赛，程序应输出格式为 ? i j 的比赛描述——一个问号后跟两个不同的选手编号。选手编号从 $1$ 到 $2n$。请记住在打印比赛描述后刷新输出。然后，你的程序应读取比赛结果——如果第一名选手的实力更强，则为大于号 (>)；如果第二名选手的实力更强，则为小于号 (<)。

你的程序最多可以组织 $4n^2$ 场比赛。在完成比赛组织后，程序应输出感叹号 (!) 并继续处理下一个测试用例，如果是最后一个测试用例则正常退出。请记住在打印感叹号后刷新输出。

必须保证：在所有与你组织的比赛结果相符的情况中，选出实力最强的 $n$ 名选手的方案有且仅有一种，但在这 $n$ 名选手内部，与比赛结果相符的实力排序方式至少有两种。

在你的程序开始组织比赛之前，评测程序会预先选定所有选手的实力值，并用这些值来回答你的询问。

样例

输入 1

2
3
>
<
>
<
>
>
3
<
<
<
>
>

输出 1

? 1 3
? 4 2
? 4 5
? 6 5
? 3 4
? 5 6
!
? 3 4
? 4 2
? 5 3
? 6 4
? 3 1
!

说明

在样例中，第一个测试用例的选手按实力从高到低排序。根据样例输出中的比赛结果，我们可以推断出选手 1、2 和 3 拥有最强的实力，但我们不知道选手 1 和选手 2 之间的实力对比。