Лаврушка і розбиття масиву

Лаврушка — сумлінний учень, який мріє стати програмістом. На останньому уроку інформатики його улюблена вчителька запропонувала йому розв’язати таке завдання. Нехай $a_1,\dots ,a_N$ — певна послідовність натуральних чисел. Лаврушці потрібно розділити послідовність чисел $1,2,3,\dots ,N$ на дві послідовності $b_1,\dots ,b_M$ і $c_1,\dots ,c_K$ таким чином, щоб:

• Кожне натуральне число $1\le r\le N$ було елементом рівно однієї з послідовностей $b$ або $c$ (тому $M+K=N$).

• Для кожної пари індексів $1\le i,j\le M$, $i\ne j$, числа $a_{b_i}$ і $a_{b_j}$ були взаємно простими.

• Для кожної пари індексів $1\le i,j\le K$, $i\ne j$, числа $a_{c_i}$ і $a_{c_j}$ були взаємно простими.

Взаємно простими називаються числа, найбільший спільний дільник яких дорівнює одиниці. Назвемо відповідний поділ послідовності $1,2,3,\dots ,N$ розбиттям послідовності $a_i$.

Розбиття послідовності може бути неоднозначне. Тому вчителька попросила Лаврушу знайти таке розбиття, що максимізує кількість елементів у послідовності $b_i$. Якщо існує кілька розбиттів, що максимізують кількість елементів у послідовності $b_i$, то потрібно знайти серед них таке, щоб послідовність $b_i$ була лексикографічно найменшою.

Будемо казати, що послідовність $q_1,q_2,\dots ,q_W$ є лексикографічно меншою за послідовність $p_1,p_2,\dots ,p_W$, якщо існує таке $i$, що $q_i<p_i$, а для довільного $j<i$ виконується $p_j=q_j$.

Завдання

Напишіть програму split, яка для заданої послідовності чисел a знайде оптимальне розбиття послідовності чисел $1,2,3,\dots ,N$ на дві послідовності $b_1,\dots ,b_M$ і $c_1,\dots ,c_K$.

Вхідні дані

У першому рядку вхідного файла записано число $Z$ ($1\le Z\le 3$) — кількість тестових вхідних даних (учителька кілька разів пропонувала Лаврушці розв’язати це завдання для різних вхідних даних).

Далі подаються $Z$ тестових даних у такому форматі.

У першому рядку даних міститься число $N$ ($1\le N\le 100000$) — кількість елементів у послідовності $a$.

У наступному рядку записано $N$ чисел, розділених одиничними пропусками, — елементи послідовності $a$ ($1\le a_i\le 2000000$).

Вихідні дані

Для кожних тестових даних виведіть у вихідний файл в одному рядку число $M$ — кількість елементів у послідовності $b$, а у другому — $M$ натуральних чисел — у порядку зростання номери елементів послідовності $a$, що увійшли до послідовності $b$.

Якщо так трапиться, що вчителька помилилась і не існує жодного розбиття послідовності $a$, то виведіть в одному рядку $-1$.

Приклади

Примітка

У першому наборі тестових даних не можна отримати розбиття, де в послідовності $b$ містилися б усі елементи $1,2,\dots ,N$, тому що числа $2$ і $4$ не взаємно прості. А в наступному наборі тестових даних взагалі не існує жодного розбиття послідовності $a$.

Оцінювання

Набір тестів складається з 4 блоків, для кожного з яких виконуються такі умови:

1. ($24$ балів): $N\le 15$; $1\le a_i\le 2000000$;

2. ($24$ балів): $N\le 1000$; $1\le a_i\le 2000000$;

3. ($30$ балів): $N\le 20000$; $1\le a_i\le 2000000$;

4. ($22$ балів): $N\le 100000$; $1\le a_i\le 2000000$.