Lavrushka and Array Splitting

Lavrushka is a dedicated student aspiring to become a programmer. In his recent computer science class, his favorite teacher presented him with an intriguing challenge. Given a sequence of natural numbers a[1], ..., a[N], Lavrushka must divide the sequence of numbers 1, 2, 3, ..., N into two sequences, b[1], ..., b[M] and c[1], ..., c[K], such that:

• Each natural number 1 ≤ r ≤ N appears in exactly one of the sequences b or c (hence M + K = N).

• For every pair of indices 1 ≤ i, j ≤ M where i ≠ j, the numbers a[bi] and a[bj] are coprime.

• For every pair of indices 1 ≤ i, j ≤ K where i ≠ j, the numbers a[ci] and a[cj] are coprime. Two numbers are considered coprime if their greatest common divisor is one. This division of the sequence 1, 2, 3, ..., N is referred to as a partition of the sequence a[i].

The partition might not be unique. Therefore, the teacher has asked Lavrushka to find a partition that maximizes the number of elements in the sequence b[i]. If multiple partitions achieve this maximum, Lavrushka should select the one where the sequence b[i] is lexicographically smallest.

A sequence q[1], q[2], ..., q[W] is lexicographically smaller than another sequence p[1], p[2], ..., p[W] if there exists an index i such that q[i] < p[i], and for all indices j < i, it holds that p[j] = q[j].

Task

Develop a program that, for a given sequence of numbers a, determines the optimal partition of the sequence of numbers 1, 2, 3, ..., N into two sequences b[1], ..., b[M] and c[1], ..., c[K].

Input Data

The first line of the input contains the number Z (1 ≤ Z ≤ 3) — the number of test cases (the teacher has given Lavrushka several sets of input data to solve).

For each test case, the first line contains the number N (1 ≤ N ≤ 100000) — the number of elements in the sequence a. The following line contains N numbers, separated by spaces, representing the elements of the sequence a (1 ≤ ai ≤ 2000000).

Output Data

For each test case, output the number M — the number of elements in the sequence b on the first line. On the second line, list M natural numbers in ascending order, representing the indices of the elements of sequence a that are included in sequence b.

If it turns out that the teacher made a mistake and no valid partition of the sequence a exists, output -1 on a single line.

Evaluation

The test set is divided into 4 blocks, each with the following conditions:

1. 24% of points: N ≤ 15, 1 ≤ a[i] ≤ 2000000.

2. 24% of points: N ≤ 1000, 1 ≤ a[i] ≤ 2000000.

3. 30% of points: N ≤ 20000, 1 ≤ a[i] ≤ 2000000.

4. 22% of points: N ≤ 100000, 1 ≤ a[i] ≤ 2000000.

Explanation. In the first test case, a partition where all elements 1, 2, ..., N are in sequence b is impossible because the numbers 2 and 4 are not coprime. In the next test case, no partition of the sequence a is possible at all.

Examples