题目描述

拉夫鲁什卡是一个认真学习、梦想成为程序员的学生。在最近一节信息学课上，他最喜欢的老师给他出了如下任务。

设 $a_1,\dots,a_N$ 是一个自然数序列。需要把数列 $1,2,3,\dots,N$ 划分为两个序列：

和

使得：

• 每个整数 $1\le r\le N$ 恰好属于序列 $b$ 或序列 $c$ 之一，因此 $M+K=N$；
• 对于任意 $1\le i,j\le M$ 且 $i\ne j$，数 $a_{b_i}$ 与 $a_{b_j}$ 互质；
• 对于任意 $1\le i,j\le K$ 且 $i\ne j$，数 $a_{c_i}$ 与 $a_{c_j}$ 互质。

若两个数的最大公约数为 $1$，称它们互质。满足上述条件的划分称为序列 $a_i$ 的一个划分。

划分可能不唯一。老师要求拉夫鲁什卡找到一个使序列 $b$ 的元素数量最大化的划分。如果有多个划分都能最大化 $b$ 的元素数量，则选择其中 $b$ 序列字典序最小的一个。

若存在某个 $i$，使得 $q_i<p_i$，且对所有 $j<i$ 都有 $q_j=p_j$，则称序列 $q_1,q_2,\dots,q_W$ 的字典序小于序列 $p_1,p_2,\dots,p_W$。

输入格式

第一行包含整数 $Z$（$1\le Z\le 3$），表示测试数据组数。

接下来给出 $Z$ 组测试数据，每组格式如下。

第一行包含整数 $N$（$1\le N\le 100000$），表示序列 $a$ 的元素个数。

第二行包含 $N$ 个整数 $a_i$（$1\le a_i\le 2000000$）。

输出格式

对于每组测试数据：

• 如果不存在任何合法划分，输出一行 -1；
• 否则第一行输出整数 $M$，表示序列 $b$ 的元素个数；第二行输出 $M$ 个自然数，按升序表示被放入序列 $b$ 的原序列下标。

数据范围与评分

测试点由 4 个子任务组成：

1. 24 分：$N\le 15$，$1\le a_i\le 2000000$；
2. 24 分：$N\le 1000$，$1\le a_i\le 2000000$；
3. 30 分：$N\le 20000$，$1\le a_i\le 2000000$；
4. 22 分：$N\le 100000$，$1\le a_i\le 2000000$。

样例

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

4
1 2 3 5 
-1

样例解释

第一组数据中，不能得到一个让 $b$ 包含全部 $1,2,\dots,N$ 的划分，因为数 $2$ 和 $4$ 不互质。第二组数据中，不存在任何合法划分。