Бұл — интерактивті есеп.

VegiCat әрбір элементі $0$, $1$ немесе $2$ болатын $a_1, a_2, \ldots, a_n$ массивін біледі. Ол массив мәндерін сізге тікелей айтқысы келмейді, бірақ оған сұрақтар қоюға болады. Әр сұранымда сіз екі $i$ және $j$ индекстерін таңдайсыз, ал VegiCat сізге $a_i > a_j$ шартының орындалатынын не орындалмайтынын айтады.

VegiCat сізден индекстерді сәйкес массив мәндерінің кемімеу ретімен шығаруды сұрайды. Яғни, келесі шартты қанағаттандыратын $1, 2, \ldots, n$ сандарының $p_1, p_2, \ldots, p_n$ орын алмастыруын табыңыз:

$$a_{p_1} \le a_{p_2} \le \cdots \le a_{p_n}.$$

Әрбір тестте ең көбі $2n - 3$ сұраным жасай аласыз.

Интерактор бейімделгіш (adaptive). Бұл массивтің алдын ала бекітілмегенін білдіреді. Интерактор осы уақытқа дейін берілген барлық жауаптарға сәйкес келетін, элементтері $\{0, 1, 2\}$ жиынынан тұратын кемінде бір массив әрқашан табылатынына кепілдік береді. Сіздің соңғы орын алмастыруыңыз барлық жауаптарға сәйкес келетін әрбір массив үшін дұрыс болуы керек.

Кіріс деректер

Бірінші жолда тесттер санын білдіретін бір бүтін сан $T$ ($1 \le T \le 250$) берілген. Одан кейін тесттердің сипаттамасы беріледі.

Әрбір тест массивтің ұзындығын білдіретін бір бүтін сан $n$-нен ($2 \le n \le 500$) басталады.

Барлық тесттер бойынша $n$ мәндерінің қосындысы $500$-ден аспайды.

Өзара әрекеттесу

Сұраным жасау үшін келесі форматта бір жол шығарыңыз:

? i j

Мұнда $1 \le i, j \le n$. Әр сұранымнан кейін бір бүтін санды оқыңыз:

• егер $a_i > a_j$ болса, $1$;
• егер $a_i \le a_j$ болса, $0$.

$i = j$ болатын сұранымдарға және қайталанатын сұранымдарға рұқсат етіледі және олар сұранымдар санына есептеледі.

Ретті анықтаған соң, келесі форматта бір жол шығарыңыз:

! p_1 p_2 ... p_n

$1$-ден $n$-ге дейінгі әрбір индекс дәл бір рет кездесуі керек. Жауапты шығару сұраным ретінде есептелмейді.

Егер жауабыңыз дұрыс болса, келесі тесттің $n$ мәнін оқып, соған өтіңіз, немесе бұл соңғы тест болса, программаны аяқтаңыз. Интерактор жауаптан кейін бөлек растау хабарламасын жібермейді.

Әрбір сұранымды немесе жауапты шығарғаннан кейін жаңа жол белгісін шығарып, шығыс буферін тазалаңыз (flush). Шығысты тазалау үшін мыналарды қолдануға болады:

• C/C++ тілдерінде fflush(stdout) немесе cout.flush();
• Java және Kotlin тілдерінде System.out.flush();
• Python тілінде sys.stdout.flush().

Егер сіз жарамсыз сұраным жасасаңыз, сұранымдар шегінен асып кетсеңіз немесе қате жауап шығарсаңыз, Wrong Answer вердиктін аласыз. Көрсетілген форматқа сәйкес келмейтін шығыс та Wrong Answer деп бағаланады. Бұл жағдайларда интерактор қате туралы жауап жіберместен жұмысын тоқтатады.

Examples

Input 1

2
3

1

1

2

0

Output 1

? 1 2

? 2 3

! 3 2 1

? 1 2

! 1 2

Note

Бірінші тестте ? 1 2 және ? 2 3 сұранымдарының екеуі де $1$ қайтарады, сондықтан $a_1 > a_2 > a_3$. Демек, $(3, 2, 1)$ — дұрыс жауап.

Екінші тестте ? 1 2 сұранымы $0$ қайтарады, сондықтан $a_1 \le a_2$. Демек, $(1, 2)$ — дұрыс жауап.