Еңбегіңе рақмет, қымбаттым. Little Cyan Fish өзінің құпия сөздерінің қаншасы жететінін білмейді, бірақ сонда да Little Cyan Fish-пен бірге осы нүктеге дейін жүріп өткенің үшін саған алғыс айтады. Соншама көп нәрсе, соншама абсурдты жайттар орын алды, Little Cyan Fish шаршады, қатты шаршады... Өткен жылы Little Cyan Fish бірнеше рет өзін-өзі құтқарماқшы болғандай сезінді, бірақ, сайып келгенде, денесіндегі жіптерді үзіп тастауға оның күші жетпеді. Little Cyan Fish әрқашан сол бір алыс жерде өз өмірінің картасын анық көре алатын тағы бір өзі бар деп елестетеді.

— «Алысқа аңсау» · Студенттер арасындағы 10-шы Қытай бағдарламалау чемпионатының финалы

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

Ал, мүмкін, мұның қаншалықты қиын болатынын байқап көрерсіз. Little Cyan Fish өз өмірін пішіні белгісіз орын алмастыру сияқты сезінеді. Адамдар әрқашан әлем кездейсоқтыққа толы дейді, бірақ неліктен Little Cyan Fish әрдайым о토шама жолы болмайды екен?.. Аха! Мүмкін, кездейсоқтық деген о토шалықты терең шығар! Сонымен, Little Cyan Fish өзінің бұл орын алмастыруы келесі жолмен кездейсоқ генерацияланады деп шешеді:

• Кездейсоқ $p_1, p_2, \dots, p_n$ орын алмастыруын генерациялау: $1$-ден $n$-ге дейінгі барлық $n!$ мүмкін орын алмастырулардың ішінен бірқалыпты кездейсоқ түрде таңдалады.
• Егер $p_1 > p_n$ болса, онда бүкіл орын алмастыруды кері аудару керек.

Сіз орын алмастырудың құрылымын тікелей бақылай алмайсыз, бірақ Little Cyan Fish сізге суперқабілет сыйлады: сұрау! Әр жолы сіз интерактивті түрде орын алмастырудағы екі санның арасындағы қашықтықтың $3$ модулі бойынша мәнін сұрай аласыз. Нақтырақ айтқанда, әр жолы сіз екі санды $u, v$ ($1 \le u, v \le n$, $u \ne v$) таңдай аласыз, сонда орын алмастыру сізге осы екі санның арасындағы қашықтықтың $3$ модулі бойынша мәнін айтады (яғни, $p_i = u, p_j = v$ болатын екі $i, j$ индексін тауып, орын алмастыру $|i - j| \bmod 3$ деп жауап береді).

Енді Little Cyan Fish сіздің не істей алатыныңызды сынап көргеніңізді қалайды. Сізге Little Cyan Fish-ке осы орын алмастыруды $25n$ сұранымнан аспайтын қадамда анықтауға көмектесу керек.

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

Бірнеше тест жағдайлары бар. Кіріс деректердің бірінші қатарында тест жағдайларының санын білдіретін бір бүтін сан $T$ ($1 \le T \le 1000$) берілген.

Әрбір тест жағдайы үшін алдымен бір бүтін санды $n$ ($3 \le n \le 10^4$) оқуыңыз керек.

Өзара әрекеттесу протоколы

Одан кейін өзара әрекеттесу басталады. Әрбір тест жағдайында сіз ең көбі $25n$ сұраным жасай аласыз. Сұраным жасау үшін сізге сұранымды сипаттайтын ? u v ($1 \le u, v \le n$, $u \ne v$) бір қатарын шығару керек. Содан кейін нәтижені стандартты кірістен оқуыңыз керек.

Жауабыңызды беру үшін ! p1 p2 ... pn шығаруыңыз керек. Сіздің шығысыңыз $p_1 < p_n$ шартын қанағаттандыруы тиіс. Жауапты шығару $25n$ сұраным шегіне есептелмейді. Жауапты шығарғаннан кейін сіз бірден келесі тест жағдайын оқуыңыз керек немесе бағдарламаңызды бірден аяқтауыңыз керек.

Сұранымды шығарғаннан кейін жаңа жол таңбасын шығаруды және шығыс ағынын тазалауды (flush) ұмытпаңыз. Ол үшін C++ тілінде fflush(stdout) немесе cout.flush(), Java тілінде System.out.flush(), Pascal тілінде flush(output), ал Python тілінде stdout.flush() қолдана аласыз.

Барлық тест жағдайлары бойынша $n$ қосындысы $10^4$-нен аспайтынына кепілдік беріледі.

Бұл есепте интерактор бейімделмейтін (non-adaptive) екеніне кепілдік беріледі. Яғни, орын алмастырулар өзара әрекеттесу процесі басталғанға дейін есеп шартында айтылғандай кездейсоқ түрде анықталады. Олар сіздің сұранымдарыңызға байланысты өзгермейді. Барлығы $30$ тест жағдайы бар (мысал тест жағдайын қоса алғанда).

Мысал

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

2
3
2
1
1
4
1
1
1
0
2

Шығыс деректер 1

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

Ескертпе

1-сурет: Little Cyan Fish және <?> <?> жерінде, 2026 жылғы 4 наурызда түсірілген