Kokalaru47 a intrat într-o nouă încurcătură! Prietenul său, Marele Anonim, şi-a cumpărat de curând o permutare $p$ de o frumuseţe nemaiauzită. Curios din fire, Kokalaru47 vrea să afle permutarea, însă Marele Anonim i-a zis doar că are lungimea $N$ şi a decis să nu dezvăluie în mod direct alte informaţii. În schimb, îi va răspunde la mai multe întrebări.

Într-o întrebare, Kokalaru47 îi dă Marelui Anonim două stringuri $A$ şi $B$ de lungime $N$. Marele Anonim creează apoi alte două stringuri $C = A{~p{~1~}~}A{~p{~2~}~}A{~p{~3~}~}...A{~p{~N~}~}$ şi $D = B{~p{~1~}~}B{~p{~2~}~}B{~p{~3~}~}...B{~p{~N~}~}$. În final, Marele Anonim răspunde la întrebare cu lungimea prefixului maximal comun dintre $C$ si $D$ în care există *cel mult o nepotrivire* între aceste două stringuri.

Într-o întrebare, Kokalaru47 îi dă Marelui Anonim două stringuri $A$ şi $B$ de lungime $N$. Marele Anonim creează apoi alte două stringuri $C = A{~p{~1~}~}A{~p{~2~}~}A{~p{~3~}~}...A{~p{~N~}~}$ şi $D = B{~p{~1~}~}B{~p{~2~}~}B{~p{~3~}~}...B{~p{~N~}~}$. În final, Marele Anonim răspunde la întrebare cu lungimea prefixului maximal comun dintre $C$ şi $D$ în care există *cel mult o nepotrivire*.

Înainte de a-i pune Marelui Anonim o întrebare, Kokalaru47 trebuie să cumpere ingredientele pentru întrebarea respectivă. El merge, aşadar, la Magazinul de Stringuri şi achizitionează 2N litere mici ale alfabetului englez (N pentru stringul A si N pentru stringul B). Se ştie că litera care apare pe pozitia c în alfabet costă c-1 parai.

Înainte de a-i pune Marelui Anonim o întrebare, Kokalaru47 trebuie să cumpere ingredientele pentru întrebarea respectivă. El merge, aşadar, la Magazinul de Stringuri şi achizitionează 2N litere mici ale alfabetului englez (N pentru stringul A şi N pentru stringul B). Se ştie că litera care apare pe pozitia $c$ în alfabet costă $c-1$ parai. De asemenea, ingredientele folosite la o întrebare nu pot fi refolosite la o altă întrebare ulterioară.

h2. Cerinţa

h2. Cerinţă

Ajutaţi-l pe Kokalaru47 să afle permutarea misterioasă fară să-şi depăşească bugetul de P parai.
h2. Interacţiune

 
h2. Date de intrare
Fişierul de intrare $shopping.in$ ...

Prima dată se va citi valoarea $T$, ce reprezintă numărul testelor ce trebuie rezolvate. Pentru fiecare test, se va citi apoi $N$, reprezentând lungimea permutării căutate.
 
Programul vostru poate pune apoi întrebări sub forma *$"? A B"$*, unde $A$ si $B$ sunt stringuri de lungime $N$. Aceste intrebari vor fi scrise in stdout. Răspunsul la o întrebare va putea fi citit din stdin.
 
Când aţi găsit permutarea căutată, afişaţi $"! p{~1~}p{~2~}p{~3~}...p{~N~}$
 
 
 

h2. Date de ieşire
În fişierul de ieşire $shopping.out$ ...

h2. Restricţii