Лаврушка — сумлінний учень, який мріє стати програмістом. На останньому уроку інформатики його улюблена вчителька запропонувала йому розв’язати таке завдання. Нехай a1, ..., aN — певна послідовність натуральних чисел. Лаврушці потрібно розділити послідовність чисел 1, 2, 3, ..., N на дві послідовності b1, ..., bM і c1, ..., cK таким чином, щоб:

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

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

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

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

Будемо казати, що послідовність q1, q2, ..., qW є лексикографічно меншою за послідовність p1, p2,..., pW, якщо існує таке i, що qi˂pi, а для довільного j˂i виконується pj = qj.

Завдання

Напишіть програму, яка для заданої послідовності чисел a знайде оптимальне розбиття послідовності чисел 1, 2, 3, …, N на дві послідовності b1, ..., bM і c1, ..., cK.

Вхідні дані

У першому рядку вхідних даних записано число 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 ≤ ai ≤ 2000000.

2. 24 % балів: N ≤ 1000, 1 ≤ ai ≤ 2000000.

3. 30 % балів: N ≤ 20000, 1 ≤ ai ≤ 2000000.

4. 22 % балів: N ≤ 100000, 1 ≤ ai ≤ 2000000.

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