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

Лаврушка — сумлінний учень, який мріє стати програмістом. На останньому уроку інформатики його улюблена вчителька запропонувала йому розв’язати таке завдання. Нехай a[1], ..., a[N] — певна послідовність натуральних чисел. Лаврушці потрібно розділити послідовність чисел 1, 2, 3, ..., N на дві послідовності b[1], ..., b[M] і c[1], ..., c[K] таким чином, щоб:

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

• Для кожної пари індексів 1 ≤ i, j ≤ M, i ≠ j, числа a[bi] і a[bj] були взаємно простими.

• Для кожної пари індексів 1 ≤ i, j ≤ K, i ≠ j, числа a[ci] і a[cj] були взаємно простими.Взаємно простими називаються числа, найбільший спільний дільник яких дорівнює одиниці. Назвемо відповідний поділ послідовності 1, 2, 3, ..., N розбиттям послідовності a[i].

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

Будемо казати, що послідовність q[1], q[2], ..., q[W] є лексикографічно меншою за послідовність p[1], p[2],..., p[W], якщо існує таке i, що q[i]˂p[i], а для довільного j˂i виконується p[j] = q[j].

####Завдання

Напишіть програму, яка для заданої послідовності чисел a знайде оптимальне розбиття послідовності чисел 1, 2, 3, …, N на дві послідовності b[1], ..., b[M] і c[1], ..., c[K].

Вхідні дані

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

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

У першому рядку даних міститься число N (1 ≤ N ≤ 100000) — кількість елементів у послідовності a. У наступному рядку записано N чисел, розділених одиничними пропусками, — елементи послідовності a (1 ≤ ai ≤ 2000000).

Вихідні дані

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

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

####Оцінювання

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

1. 24 % балів: N ≤ 15, 1 ≤ a[i] ≤ 2000000.

2. 24 % балів: N ≤ 1000, 1 ≤ a[i] ≤ 2000000.

3. 30 % балів: N ≤ 20000, 1 ≤ a[i] ≤ 2000000.

4. 22 % балів: N ≤ 100000, 1 ≤ a[i] ≤ 2000000.

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

Приклади