这是一个交互式题目。

大海，我们又见面了。希望你在接下来的暑假里也能开心！ 很久很久以前，Una 和 Kamome 就已经是好朋友了。

她们喜欢玩猜游戏。上次，Una 发明的游戏被 Kamome 出色的策略轻松破解了。这一次，Una 带来了一个新游戏。

Una 心中有一棵包含 $n$ 个节点的树。Kamome 最多可以进行 $n$ 次询问：

• Kamome 可以告诉 Una 一个 $0 \sim n-1$ 的排列 $P_1, P_2, \dots, P_n$（其中 $0 \le P_i \le n-1$ 且所有 $P_i$ 互不相同）。然后 Una 会告诉 Kamome，当节点 $i$ 被赋予权值 $2^{P_i}$ 时，这棵树的带权直径长度。

但有时 Kamome 会发现 Una 在捣乱。更具体地，存在无论问多少次都无法唯一确定树的情况。在这些情况下，Kamome 可以报告无解。

交互协议

这是一个交互式题目。每次输出后，你都需要刷新输出缓冲区。要刷新输出缓冲区，可以使用：

• C/C++：fflush(stdout) 或 cout.flush()
• Java 和 Kotlin：System.out.flush()
• Python：sys.stdout.flush()

首先，你需要读取测试用例的数量 $T$（$1 < T < 10^4$）。 对于每个测试用例，你需要读取树的大小 $n$（$2 \le n \le 100$，$\sum n^2 < 10^6$）。

要进行询问，你需要输出一行，格式为 ? P1 P2 ... Pn（其中 $0 \le P_i \le n-1$，且对于 $1 < i < j \le n$ 有 $P_i \ne P_j$）。 然后，读取一个长度为 $n$ 的二进制表示字符串，表示树的带权直径。如果询问无效，或者在一个测试用例中进行了超过 $n$ 次询问，评测程序将输出 -1。如果你读取到 -1，必须立即终止程序以避免未定义行为。

如果你确定无法唯一确定这棵树，必须输出 ! NO。 否则，你必须输出一行，格式为 ! YES u1 v1 u2 v2 ... un-1 vn-1，表示树中包含边 $(u_i, v_i)$。边可以按任意顺序输出。

然后，读取单词 OK 或 WA，表示你的答案是否正确。如果你读取到 WA，必须立即终止程序以避免未定义行为。 如果树无法唯一确定而你输出了 YES，即使你给出的答案是正确的，Una 也会认为你在作弊，因此你的答案会被判定为错误解答（WA）。

评测程序是非适应性的，因此答案不会在询问后发生改变。

样例

输入格式 1

2
4
1110
1110
OK
3
111
OK

输出格式 1

? 0 1 2 3
? 2 1 0 3
! YES 1 4 2 4 3 4
? 0 1 2
! NO

说明

提供了一个测试工具以帮助参赛者开发和测试其解决方案。你可以从附加文件中下载此工具。使用 -h 选项运行该工具可以说明其用法。测试工具仅实现真实评测程序的部分功能和部分测试场景。