题目描述

交互器为每组数据隐藏了一个排列 $p$，它由 $0,1,2,\ldots,n-1$ 组成。你的任务是输出两个下标 $x,y$，允许 $x=y$，并保证 $p_x=0$ 或 $p_y=0$。

你可以询问两个不同下标 $i,j$，交互器会返回 $\gcd(p_i,p_j)$。每组数据最多允许询问 $2n$ 次。

输入格式

交互开始时，交互器先给出测试组数 $t$。每组交互开始前，交互器会给出本组的 $n$。

本地交互器的隐藏输入采用如下格式：第一行是 $t$；每组数据第一行是 $n$，第二行是排列 $p_1,p_2,\ldots,p_n$。

输出格式

询问时输出一行 ? i j，要求 $1\le i,j\le n$ 且 $i\ne j$，然后刷新输出；交互器会返回 $\gcd(p_i,p_j)$。

回答时输出一行 ! x y。若 $p_x=0$ 或 $p_y=0$，交互器返回 $1$ 并进入下一组；否则返回 $-1$。

样例

2
2
1
1
5
2
4
1

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

样例说明

样例是交互记录。第一组隐藏排列可为 $[1,0]$，第二组隐藏排列可为 $[2,4,0,1,3]$。

数据范围

$1\le t\le 10^4$，$2\le n\le 2\times 10^4$，所有测试组的 $n$ 之和不超过 $2\times 10^4$。每组询问次数不超过 $2n$。