Это интерактивная задача с двойным запуском (коммуникационная).

Участвуют два игрока: Призрак Джа и Утёнок Кряк. Жюри (иначе известное как интерактор данной задачи) сначала взаимодействует с Джа. После того как Джа завершает взаимодействие, жюри взаимодействует с Кряком. Обратите внимание, что Джа и Кряк не могут напрямую передавать информацию друг другу; оба игрока могут только отправлять информацию жюри или получать её от жюри.

До начала взаимодействия жюри определяет целое число $$$n$$$ и массив из $$$n$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$. Эти значения одинаковы для обоих игроков.

Джа получает от жюри $$$n$$$ и массив из $$$n$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_n$$$, который он хочет передать Кряку, где $$$a_i \le 10^6$$$. Для этого Джа выбирает целое число $$$k$$$ такое, что $$$$$$k \le \left\lceil \frac{10n}{9} \right\rceil + 150,$$$$$$ и создаёт массив целых положительных чисел $$$b_1, b_2, \ldots, b_k$$$, где $$$b_i \le 10^6$$$, и отправляет его жюри. Затем жюри передаёт Кряку целые числа $$$n$$$ и $$$k$$$. Кряк может задать жюри не более $$$180n + 150$$$ запросов следующего вида:

• Выбрать любые два целых числа $$$i$$$ и $$$j$$$ ($$$1 \le i, j \le k$$$, $$$i \neq j$$$), и жюри ответит значением $$$\mathrm{gcd}(b_i, b_j)$$$.

Здесь $$$\gcd(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

Обратите внимание, что оба массива $$$a$$$ и $$$b$$$ скрыты от Кряка; Кряк может получать информацию только из запросов.

Джа хочет гарантировать, что Кряк сможет определить исходный массив $$$a$$$. Ваша задача — выступить в роли обоих игроков и определить оптимальную стратегию взаимодействия для обоих игроков, чтобы Кряк правильно определил исходный массив $$$a$$$.

Первый запуск

Ваш код будет запущен ровно дважды на каждом тесте. В первом запуске вы — Джа.

Входные данные

Первая строка входных данных содержит строку first. Это нужно для того, чтобы ваша программа поняла, что это первый запуск, и действовала как Джа.

Во второй строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка $$$i$$$-го набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^3$$$) — длину массива $$$a$$$ для $$$i$$$-го набора входных данных.

Вторая строка $$$i$$$-го набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — массив $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$10^3$$$.

Выходные данные

Для каждого набора входных данных сначала выведите целое число $$$k$$$ ($$$1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$$$), обозначающее длину массива $$$b$$$. Затем выведите $$$k$$$ целых чисел $$$b_1, b_2, \ldots, b_k$$$ ($$$1 \le b_i \le 10^6$$$), обозначающих массив $$$b$$$, который Джа отправит жюри. Этот массив будет использоваться для ответа на запросы во втором запуске.

После этого перейдите к следующему набору входных данных или завершите программу, если это был последний набор.

Второй запуск

Во втором запуске вы — Кряк.

Входные данные

Первая строка входных данных содержит строку second. Это нужно для того, чтобы ваша программа поняла, что это второй запуск, и действовала как Кряк.

Вторая строка входных данных содержит ровно одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Обратите внимание, что это число равно $$$t$$$ из входных данных первого запуска.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 10^3$$$, $$$1 \le k \le \left\lceil \frac{10n}{9} \right\rceil + 150$$$). Это обозначает длины массивов $$$a$$$ и $$$b$$$ соответственно.

Обратите внимание, что наборы входных данных во втором запуске могут быть перемешаны. Для дополнительной иллюстрации смотрите пример.

Взаимодействие

Для $$$i$$$-го набора входных данных напомним, что сначала вы получаете $$$n$$$ и $$$k$$$ от жюри согласно описанному выше формату входных данных. После получения этих данных вы можете задать не более $$$180n + 150$$$ запросов следующего вида:

• ? i j ($$$1 \leq i, j \leq k$$$, $$$i \neq j$$$).

После каждого запроса жюри ответит значением $$$\mathrm{gcd}(b_i, b_j)$$$, которое вы должны считать из входного потока.

Если ваша программа задаст более $$$180n + 150$$$ запросов, она должна немедленно завершиться и получит вердикт Wrong Answer. В противном случае вы можете получить произвольный вердикт, так как ваше решение продолжит читать из закрытого потока.

Когда вы готовы сообщить исходный массив $$$a$$$, вы можете сделать это в следующем формате:

• ! $$$a_1, a_2, \ldots ,a_n$$$ ($$$1 \leq a_i \leq 10^6$$$).

После этого перейдите к следующему набору входных данных или завершите программу, если все наборы обработаны.

Интерактор не является адаптивным. То есть оба массива $$$a$$$ и $$$b$$$ не изменятся в ходе взаимодействия и всегда будут теми же массивами, что и в первом запуске.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.