Лаврушка и разбиение массива

Лаврушка — старательный ученик, мечтающий стать программистом. На последнем уроке информатики его любимая учительница предложила ему решить следующую задачу. Пусть дана последовательность натуральных чисел 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], то нужно выбрать то, где последовательность b[i] является лексикографически наименьшей.

Будем говорить, что последовательность 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 ≤ a[i] ≤ 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.