Lavrushka and Array Splitting#7667

Lavrushka and Array Splitting

1 second

64 megabytes

Easy

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}, \dots, a_{N}$ a_1, \ldots, a_N, Lavrushka must divide the sequence of numbers $1, 2, 3, \dots, N$ 1, 2, 3, \ldots, N into two sequences, $b_{1}, \dots, b_{M}$ b_1, \ldots, b_M and $c_{1}, \dots, c_{K}$ c_1, \ldots, c_K, such that:

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

• For every pair of indices $1 \leq i, j \leq M$ 1 \leq i, j \leq M where $i \neq = j$ i \neq j, the numbers $a_{b_{i}}$ a_{b_i} and $a_{b_{j}}$ a_{b_j} are coprime.

• For every pair of indices $1 \leq i, j \leq K$ 1 \leq i, j \leq K where $i \neq = j$ i \neq j, the numbers $a_{c_{i}}$ a_{c_i} and $a_{c_{j}}$ a_{c_j} are coprime.

Two numbers are considered coprime if their greatest common divisor is one. This division of the sequence $1, 2, 3, \dots, N$ 1, 2, 3, \ldots, N is referred to as a partition of the sequence $a_{i}$ 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}$ b_i. If multiple partitions achieve this maximum, Lavrushka should select the one where the sequence $b_{i}$ b_i is lexicographically smallest.

A sequence $q_{1}, q_{2}, \dots, q_{W}$ q_1, q_2, \ldots, q_W is lexicographically smaller than another sequence $p_{1}, p_{2}, \dots, p_{W}$ p_1, p_2, \ldots, p_W if there exists an index $i$ such that $q_{i} < p_{i}$ q_i < p_i, and for all indices $j < i$ j < i, it holds that $p_{j} = q_{j}$ p_j = q_j.

Develop a program that, for a given sequence of numbers $a$ , determines the optimal partition of the sequence of numbers $1, 2, 3, \dots, N$ 1, 2, 3, \ldots, N into two sequences $b_{1}, \dots, b_{M}$ b_1, \ldots, b_M and $c_{1}, \dots, c_{K}$ c_1, \ldots, c_K.

Input

The first line of the input contains the number $Z$ ( $1 \leq Z \leq 3$ 1 \leq Z \leq 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 \leq N \leq 100000$ 1 \leq N \leq 100\,000) — 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 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000).

Output

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.

Examples

Example 1

Note

In the first test case, a partition where all elements $1, 2, \dots, N$ 1, 2, \ldots, 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.

Scoring

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

$1.$ $24%$ of points: $N \leq 15$ N \leq 15, $1 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000.

$2.$ $24%$ of points: $N \leq 1000$ N \leq 1000, $1 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000.

$3.$ $30%$ of points: $N \leq 20000$ N \leq 20\,000, $1 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000.

$4.$ $22%$ of points: $N \leq 100000$ N \leq 100\,000, $1 \leq a_{i} \leq 2000000$ 1 \leq a_i \leq 2\,000\,000.