题目描述

题目译自 Ukrainian Olympiads in Informatics 2016 Stage 4 Day2 T3. Лаврушка і розбиття масиву

拉夫鲁什卡是一名勤奋好学的学生，梦想成为一名程序员。在最近一节信息学课上，他敬爱的老师给他出了这样一道题。给定一个自然数序列 $a_1, \dots, a_N$。拉夫鲁什卡需要将数字序列 $1, 2, 3, \dots, N$ 划分为两个序列 $b_1, \dots, b_M$ 和 $c_1, \dots, c_K$，使得：

• 每个自然数 $1 \leq r \leq N$ 都恰好是序列 $b$ 或序列 $c$ 中的一个元素（因此 $M + K = N$）。
• 对于任意一对索引 $1 \leq i, j \leq M, i \neq j$，数 $a_{b_i}$ 和 $a_{b_j}$ 都是互质的。
• 对于任意一对索引 $1 \leq i, j \leq K, i \neq j$，数 $a_{c_i}$ 和 $a_{c_j}$ 都是互质的。

互质数是指最大公约数等于 $1$ 的数。我们将对序列 $1, 2, 3, \dots, N$ 的这种划分称为序列 $a_i$ 的一个划分。

序列的划分可能不唯一。因此，老师要求拉夫鲁什卡找到一个能使序列 $b_i$ 中元素数量最大化的划分。如果存在多个能使序列 $b_i$ 元素数量最大化的划分，则需要在这些划分中找到一个，使得序列 $b_i$ 的字典序最小。

我们称序列 $q_1, q_2, \dots, q_W$ 的字典序小于序列 $p_1, p_2, \dots, p_W$，如果存在一个索引 $i$，使得 $q_i<p_i$，并且对于任意的 $j<i$，都有 $p_j=q_j$。

请编写一个名为 split 的程序，对于给定的数字序列 $a$，找到将数字序列 $1, 2, 3, \dots, N$ 划分为两个序列 $b_1, \dots, b_M$ 和 $c_1, \dots, c_K$ 的最优划分。

输入格式

输入文件的第一行包含一个数字 $Z$ $(1 \leq Z \leq 3)$，测试数据的数量。

接下来是 $Z$ 组测试数据，格式如下。

数据的第一行包含一个数字 $N$ $(1 \leq N \leq 100000)$，表示序列 $a$ 中的元素数量。

下一行包含 $N$ 个用单个空格分隔的数字，表示序列 $a$ $(1 \leq a_i \leq 2000000)$ 的元素。

输出格式

对于每组测试数据，向输出文件的一行中输出一个数字 $M$，表示序列 $b$ 中的元素数量，在第二行中输出 $M$ 个自然数，表示按升序排列的、被分入序列 $b$ 的序列 $a$ 的元素编号。

如果碰巧老师弄错了，不存在任何对序列 $a$ 的划分，则在单独一行中输出 $-1$。

2
5
1 2 3 4 5
5
2 3 4 5 6

4
1 2 3 5 
-1

数据范围与提示

详细子任务附加限制及分值如下表所示：