CF1483B.Playlist

Arkady has a playlist that initially consists of $n$ songs, numerated from $1$ to $n$ in the order they appear in the playlist. Arkady starts listening to the songs in the playlist one by one, starting from song $1$. The playlist is cycled, i. e. after listening to the last song, Arkady will continue listening from the beginning.

Each song has a genre $a_i$, which is a positive integer. Let Arkady finish listening to a song with genre $y$, and the genre of the next-to-last listened song be $x$. If $\operatorname{gcd}(x, y) = 1$, he deletes the last listened song (with genre $y$) from the playlist. After that he continues listening normally, skipping the deleted songs, and forgetting about songs he listened to before. In other words, after he deletes a song, he can't delete the next song immediately.

Here $\operatorname{gcd}(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$.

For example, if the initial songs' genres were $[5, 9, 2, 10, 15]$, then the playlist is converted as follows: [5, 9, 2, 10, 15] $\to$ [5, 9, 2, 10, 15] $\to$ [5, 2, 10, 15] (because $\operatorname{gcd}(5, 9) = 1$) $\to$ [5, 2, 10, 15] $\to$ [5, 2, 10, 15] $\to$ [5, 2, 10, 15] $\to$ [5, 2, 10, 15] $\to$ [5, 2, 10, 15] $\to$ [5, 10, 15] (because $\operatorname{gcd}(5, 2) = 1$) $\to$ [5, 10, 15] $\to$ [5, 10, 15] $\to$ ... The bold numbers represent the two last played songs. Note that after a song is deleted, Arkady forgets that he listened to that and the previous songs.

Given the initial playlist, please determine which songs are eventually deleted and the order these songs are deleted.

阿尔卡季有一个初始包含 $n$ 首歌曲的播放列表，这些歌曲按其在播放列表中出现的顺序编号为 $1$ 至 $n$。阿尔卡季从第 $1$ 首歌开始依次收听这些歌曲。该播放列表是循环播放的，即听完最后一首歌后，他将回到开头继续收听。

每首歌曲有一个类型 $a_i$，它是一个正整数。假设阿尔卡季刚刚听完一首类型为 $y$ 的歌曲，而倒数第二首已听完的歌曲类型为 $x$。若 $\operatorname{gcd}(x, y) = 1$，则他将最后听完的那首歌（类型为 $y$）从播放列表中删除。随后他照常继续收听，跳过已被删除的歌曲，并且“遗忘”所有此前已听过（包括刚被删除的那首）的歌曲。换言之，在删除一首歌之后，他不能立即删除下一首歌。

此处 $\operatorname{gcd}(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数（GCD）。

例如，若初始歌曲类型序列为 $[5, 9, 2, 10, 15]$，则播放列表的变化过程如下：

5, 9, 2, 10, 15$$ $\to$ $$5, 9, 2, 10, 15$$ $\to$ $$5, 2, 10, 15$$（因为 $\operatorname{gcd}(5, 9) = 1$）$\to$ $$5, 2, 10, 15$$ $\to$ $$5, 2, 10, 15$$ $\to$ $$5, 2, 10, 15$$ $\to$ $$5, 2, 10, 15$$ $\to$ $$5, 2, 10, 15$$ $\to$ $$5, 10, 15$$（因为 $\operatorname{gcd}(5, 2) = 1$）$\to$ $$5, 10, 15$$ $\to$ $$5, 10, 15$$ $\to$ … 其中加粗的数字表示最近播放的两首歌曲。注意：每当一首歌被删除后，阿尔卡季便“遗忘”了自己曾听过该歌及之前的所有歌曲。 给定初始播放列表，请确定最终被删除的歌曲有哪些，以及它们被删除的顺序。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). Description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the number of songs.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the genres of the songs.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10\,000$）。随后是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 歌曲的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$）—— 歌曲的类型。

保证所有测试用例中 $n$ 的总和不超过 $10^5$。

For each test case, print a single line. First, print a single integer $k$ — the number of deleted songs. After that print $k$ distinct integers: deleted songs in the order of their deletion.

对于每个测试用例，输出一行。首先，输出一个整数 $k$ —— 被删除的歌曲数量；然后输出 $k$ 个互不相同的整数：按删除顺序排列的被删除歌曲编号。

Explanation of the first test case is given in the statement.

In the second test case, the playlist is converted as follows: [1, 2, 4, 2, 4, 2] $\to$ [1, 2, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2] (because $\operatorname{gcd}(1, 2) = 1$) $\to$ [1, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2] $\to$ [4, 2, 4, 2] (because $\operatorname{gcd}(2, 1) = 1$) $\to$ [4, 2, 4, 2] $\to$ ...

In the third test case, the playlist is converted as follows: [1, 2] $\to$ [1, 2] $\to$ [1] (because $\operatorname{gcd}(1, 2) = 1$) $\to$ [1] $\to$ [1] (Arkady listened to the same song twice in a row) $\to$ [] (because $\operatorname{gcd}(1, 1) = 1$).

The fourth test case is same as the third after deletion of the second song.

In the fifth test case, the same song is listened to over and over again, but since $\operatorname{gcd}(2, 2) \ne 1$, it is not deleted.

第一个测试用例的解释已在题面中给出。

在第二个测试用例中，播放列表按如下方式转换：
[1, 2, 4, 2, 4, 2] $\to$ [1, 2, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2]（因为 $\operatorname{gcd}(1, 2) = 1$）$\to$ [1, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2] $\to$ [1, 4, 2, 4, 2] $\to$ [4, 2, 4, 2]（因为 $\operatorname{gcd}(2, 1) = 1$）$\to$ [4, 2, 4, 2] $\to$ ...

在第三个测试用例中，播放列表按如下方式转换：
[1, 2] $\to$ [1, 2] $\to$ [1]（因为 $\operatorname{gcd}(1, 2) = 1$）$\to$ [1] $\to$ [1]（Arkady 连续两次收听了同一首歌曲）$\to$ []（因为 $\operatorname{gcd}(1, 1) = 1$）。

第四个测试用例在删除第二首歌曲后，与第三个测试用例相同。

在第五个测试用例中，同一首歌曲被反复收听，但由于 $\operatorname{gcd}(2, 2) \ne 1$，它不会被删除。