Description

这是一道交互题。

你是一家国际象棋俱乐部的总教练。俱乐部共有 $2n$ 名选手，每位选手都有一个独特的实力值（用数字表示），但这些实力值对你来说是未知的。

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

为此，你可以组织选手之间的比赛。每场比赛你需要选择两名选手进行对决，之后你会知道两人中谁的实力更强。你可以根据比赛结果来决定下一场比赛的参与者。

但你不希望完全了解这 $n$ 名选手之间的具体实力排名，因为那样会让锦标赛本身变得不够引人入胜。更正式地说，你需要达到这样一种状态：根据已进行的比赛结果，恰好存在一种方式可以选出实力最强的 $n$ 名选手，但同时这些选手之间至少存在两种不同的实力排名顺序与比赛结果一致。

交互协议

你的程序需要处理多个测试用例。首先读取整数 $t$（$t \ge 1$）表示测试用例数量，然后依次处理每个测试用例。

在每个测试用例中：

1. 首先读取整数 $n$（$3 \le n \le 100$），表示需要从 $2n$ 名选手中选出 $n$ 名。所有测试用例的 $n$ 的平方和不超过 $10\,000$。
2. 然后可以组织若干场比赛。要组织比赛，需要输出格式为 ? i j 的指令（问号后跟两个不同的选手编号）。选手编号为 $1$ 到 $2n$。输出后需要刷新输出缓冲区。
3. 之后读取比赛结果：> 表示第一个选手更强，< 表示第二个选手更强。
4. 最多可以组织 $4n^2$ 场比赛。结束后输出 ! 并处理下一个测试用例（或结束程序）。输出 ! 后也需要刷新输出缓冲区。

最终必须满足：

• 根据比赛结果，恰好有一种方式可以选出实力最强的 $n$ 名选手
• 但这些选手之间至少存在两种可能的实力排名顺序与比赛结果一致

评测系统会在程序开始前为所有选手分配不同的实力值，并根据这些值回答比赛结果。

Input Format

参见交互协议。

Output Format

参见交互协议。

2
3

>

<

>

<

>

>

3

<

<

<

>

>

? 1 3

? 4 2

? 4 5

? 6 5

? 3 4

? 5 6

!

? 3 4

? 4 2

? 5 3

? 6 4

? 3 1

!

Hint

在第一个测试用例中，选手按实力降序排列。根据示例中的比赛结果可以确定选手 1、2、3 是最强的三人，但我们无法确定选手 1 和 2 之间的具体强弱关系。

翻译由 DeepSeek V3 完成