Este é um problema interativo. Lembra-te de esvaziar o buffer de saída após cada impressão. Para isso, podes usar:

• fflush(stdout) ou cout.flush() em C/C++;
• System.out.flush() em Java e Kotlin;
• sys.stdout.flush() em Python;
• Consulta a documentação para outras linguagens.

Little Cyan Fish tem uma permutação secreta $p_0,p_1,\ldots,p_n$ de comprimento $n+1$, composta pelos inteiros de $0$ a $n$. Ele quer que adivinhes a permutação secreta. Para isso, Little Cyan Fish permite-te realizar no máximo $1024$ consultas da seguinte forma:

• ? i j: Obtém o índice $k$ ($0\le k\le n$) tal que $p_k=|p_i-p_j|$.

Naturalmente, para uma consulta ser válida, deves garantir que $i$ e $j$ são dois inteiros em $[0,n]$. Por exemplo, se $p_0=2,p_1=0,p_2=1$, a consulta ? 0 2 devolve o índice $2$, pois $|p_0-p_2|=|2-1|=1=p_2$.

Little Cyan Fish quer que cries uma estratégia para encontrar a permutação. Naturalmente, não quer que ganhes o jogo com demasiada facilidade. Por isso, irá alterar adaptativamente a permutação $p$ para te apanhar numa armadilha (consulta «Interação» para mais pormenores).

Entrada

Há vários casos de teste. A primeira linha da entrada contém um único inteiro $T$ ($1\le T\le100$), indicando o número de casos de teste.

Para cada caso de teste, a primeira linha da entrada contém um único inteiro $n$ ($1\le n\le1000$). Depois, começa a interação.

Interação

Para fazer uma consulta, imprime uma linha no seguinte formato:

$$?\ i\ j$$

Aqui $i$ e $j$ são dois inteiros de $0$ a $n$. Deves garantir que o número de consultas não excede $1024$. Como resposta, receberás um inteiro $k$ tal que $p_k=|p_i-p_j|$.

Para comunicar a resposta, imprime uma linha no seguinte formato:

$$!\ p_0\ p_1\ \ldots\ p_n$$

Aqui $p$ é a permutação que pretendes comunicar.

Depois de imprimir uma consulta ou comunicar a resposta, não te esqueças de imprimir uma mudança de linha e esvaziar o fluxo de saída.

Neste problema, o interator é adaptativo. Isto significa que a permutação $p$ pode mudar consoante as tuas consultas, desde que não contradiga as consultas anteriores.

Exemplos

Exemplo de interação 1

Ler:

1
3

Escrever:

? 2 2

Ler:

1

Escrever:

? 0 3

Ler:

3

Escrever:

! 2 0 3 1

Ferramenta de teste: É fornecida uma ferramenta para ajudar os participantes a desenvolver e testar as suas soluções. Podes descarregá-la dos anexos. Executá-la com a opção -h deverá descrever como a utilizar. A ferramenta implementa apenas alguns cenários de teste e parte das funcionalidades do programa de avaliação real.