问题描述

光头强有 $n$ 个砝码，其中有一个是劣质砝码，稍稍轻一点，其余砝码一样重。你还有一个天平，每次你可以任选若干个砝码放到天平的两侧进行称重，请问最少需要称多少次才能确保将劣质的一个找出来？光头强心里算了一下，认为是 $X$ 次。

你需要告诉光头强一个数字 $x$ 表示你认为最少需要称多少次才能确保找出劣质砝码。如果你输出的数值比 $X$ 大，那么你会直接得到 WA 的结果。当然，如果你输出的次数小于等于 $x$，那么你必须找出缺陷砝码，以证明你的做法是可行的。

当然，由于光头强怕你作弊，所以必须由他来称重，你只需要告诉他怎么放置砝码即可。

询问：? L R，表示你让他在左边放置 $L$ 个砝码，在右边放置 $R$ 个砝码。

接下来一行你需要输出 $L$ 个数，再输出 $R$ 个数，分别表示放置在左边和右边的砝码编号，不得有重复。

光头强会告诉你称重结果：

• < 表示 $W_L<W_R$，即左侧轻。
• > 表示 $W_L>W_R$，即右侧轻。
• = 表示 $W_L=W_R$，即两边一样。

询问方式

第一行输出一个整数 $x$，表示最少需要称多少次才能确保找出劣质砝码。

询问方式如前面所述。询问次数不得超过你给出的 $x$。

当你确定了答案之后，请输出：! a：

这里 $a$ 是你认为的劣质砝码。

系统输出

系统输出的第一行是一个整数 $T(1≤T≤1000)$，表示测试数据的组数。每组测试数据，系统首先输出一个整数 $n(1≤n≤10^5)$，表示该组测试数据的砝码数，然后你可以按规定进行交互。

系统根据实际情况，返回 <，= 或 >。

一组数据交互完成后，系统再输出下一个 $n$。

数据保证单个测试点有 $\sum n≤2×10^5$。

样例

3

4
<
>

100
=
=
=
=
<

100
<
=
>

2
? 2 2
1 2 3 4
? 1 1
1 2
! 2

5
? 1 1
1 2
? 1 1
3 4
? 1 1
5 6
? 1 1
7 8
? 5 5
1 3 5 7 9 2 4 6 8 10
! 9

4
? 1 1
1 2
? 1 1
3 4
? 2 1
1 2 3
! 1

样例说明

注意，上述空行是为了展示方便，实际系统输出并没有。后台采取忽略空格和空行的读取方式，你也不需要输出空行。

Case1：后台产生的数字是 2。

• 第一次查询 $12vs34$，告诉你左边轻。
• 第二次查询 $1vs2$，告诉你右边轻。锁定了结果。
• 找到了结果，为 2。

Case2：后台产生的数字是 9。

• 第一次查询 $1vs2$，不分伯仲。
• 第二次查询 $3vs4$，不分伯仲。
• 第三次查询 $5vs6$，不分伯仲。
• 第四次查询 $7vs8$，不分伯仲。
• 第五次查询 $13579vs2468X$，左边轻，由于我们已经知道$1=2、3=4、5=6、7=8$，所以可以推算出来$9<10$。
• 找到了结果，为 9。

Case3：后台产生的数字是 1。

• 第一次查询 $1vs2$，分出胜负。
• 第二次查询 $3vs4$，你不想浪费免费测试机会，所以你继续测试。
• 第三次查询 $12vs3$，砝码多的自然重。
• 虽然你可以查询 4 次，但你觉得累了，输出了结果 1。

注意事项。

如果使用带缓冲的输出，务必进行flush，否则可能导致后台交互器不能即时读取到数据导致超时。