Arkady 有一个播放列表,最初由 $$$n$$$ 歌曲组成,按照播放列表中出现的顺序从 $$$1$$$ 到 $$$n$$$ 进行编号。 Arkady 开始一首一首地听播放列表中的歌曲,从歌曲 $$$1$$$ 开始。播放列表是循环播放的,即。 e.听完最后一首歌后,阿尔卡迪将从头开始继续听。
每首歌曲都有一个流派 $$$a_i$$$,它是一个正整数。让 Arkady 听完一首风格为 $$$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$$$ ... 粗体数字代表最后播放的两首歌曲。请注意,删除歌曲后,阿尔卡迪会忘记他听过该歌曲和之前的歌曲。
给定初始播放列表,请确定最终删除哪些歌曲以及这些歌曲的删除顺序。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,打印一行。首先,打印一个整数 $$$k$$$ — 已删除歌曲的数量。之后打印 $$$k$$$ 不同的整数:按删除顺序删除歌曲。
示例
输入 #1
5 5 5 9 2 10 15 6 1 2 4 2 4 2 2 1 2 1 1 1 2
输出 #1
2 2 3 2 2 1 2 2 1 1 1 0
注意
声明中给出了第一个测试用例的解释。
在第二个测试用例中,播放列表转换如下: [1, 2, 4, 2, 4, 2] $$$\to$$$ [1, 2, 4, 2, 4, 2] $$$\to$$$ [1, 4, 2, 4, 2] (因为 $$$\operatorname{gcd}(1, 2) = 1$$$) $$$\到$$$ [1, 4, 2, 4, 2] $$$\到$$$ [1, 4, 2, 4, 2] $$$\到$$$ [1, 4, 2, 4, 2] $$$\到$$$ [1, 4, 2, 4, 2] $$$\到$$$ [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$$$,因此没有被删除。