D. Плейлист
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Аркадия есть плейлист, в котором изначально $$$n$$$ песен, пронумерованных от $$$1$$$ до $$$n$$$ в том порядке, в котором они находятся в плейлисте. Аркадий начинает слушать песни из плейлиста друг за другом, начиная с песни $$$1$$$. Плейлист зациклен, то есть после того, как он прослушает последнюю песню, он опять начнет слушать с начала плейлиста.

У каждой песни есть жанр, определяемый натуральным числом $$$a_i$$$. Пусть Аркадий только что прослушал песню с жанром $$$y$$$, а до нее — песню с жанром $$$x$$$. Если $$$\operatorname{gcd}(x, y) = 1$$$, он думает, что песни не сочетаются, и удаляет последнюю прослушанную песню (с жанром $$$y$$$) из плейлиста. После этого он продолжает слушать песни как обычно, пропуская уже удаленные, при этом он забывает, что слушал какие-то песни до удаления. Иными словами, он не может удалить песню сразу после того, как удалил предыдущую. Здесь $$$\operatorname{gcd}(x, y)$$$ обозначает наибольший общий делитель (НОД) чисел $$$x$$$ и $$$y$$$.

Например, если жанры песен в начальном плейлисте равны $$$[5, 9, 2, 10, 15]$$$, то прослушивание происходит следующим образом: [5, 9, 2, 10, 15] $$$\to$$$ [5, 9, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] (т. к. $$$\operatorname{gcd}(5, 9) = 1$$$) $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 2, 10, 15] $$$\to$$$ [5, 10, 15] (т. к. $$$\operatorname{gcd}(5, 2) = 1$$$) $$$\to$$$ [5, 10, 15] $$$\to$$$ [5, 10, 15] $$$\to$$$ ... Жирным выделены последние две прослушанные песни. Обратите внимание, после удаления некоторой песни Аркадий забывает, что слушал ее и предыдущую.

Вам дан начальный плейлист, определите, какие песни будут в итоге удалены и в каком порядке.

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

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

Первая строка набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — количество песен.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — жанры песен.

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

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

Для каждого набора входных данных выведите одну строку. Сначала выведите одно целое число $$$k$$$ — количество песен, которые будут удалены. Затем выведите $$$k$$$ различных целых чисел — номера удаленных песен в порядке удаления.

Пример
Входные данные
5
5
5 9 2 10 15
6
1 2 4 2 4 2
2
1 2
1
1
1
2
Выходные данные
2 2 3 
2 2 1 
2 2 1 
1 1 
0
Примечание

Первый набор входных данных объяснен в условии.

Во втором наборе плейлист изменяется следующим образом: [1, 2, 4, 2, 4, 2] $$$\to$$$ [1, 2, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] (т. к. $$$\operatorname{gcd}(1, 2) = 1$$$) $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] $$$\to$$$ [4, 2, 4, 2] (т. к. $$$\operatorname{gcd}(2, 1) = 1$$$) $$$\to$$$ [4, 2, 4, 2] $$$\to$$$ ...

Во третьем наборе плейлист изменяется следующим образом: [1, 2] $$$\to$$$ [1, 2] $$$\to$$$ [1] (т. к. $$$\operatorname{gcd}(1, 2) = 1$$$) $$$\to$$$ [1] $$$\to$$$ [1] (Аркадий послушал одну и ту же песню подряд дважды) $$$\to$$$ [] (т. к. $$$\operatorname{gcd}(1, 1) = 1$$$).

Четвертый набор входных данных совпадает с предыдущим после удаления второй песни.

В пятом примере Аркадий слушает одну и ту же песню снова и снова, но т. к. $$$\operatorname{gcd}(2, 2) \ne 1$$$, он не удаляет ее.