Rayan 做出了最后的努力,声称自己比 Rayaneh(即波斯语中的计算机)更强大,以赢得 Reyhaneh 的心。为了验证这一点,雷哈内向花剌子米寻求帮助。 Khwarizmi 解释说,如果集合中没有元素可以写成其他元素的整数线性组合,则集合是整数线性无关的。每次给 Rayan 一组整数,并且必须识别最大可能整数线性独立子集之一。
请注意,单个元素始终被视为整数线性独立子集。
$$$a_1, \ldots, a_k$$$ 的整数线性组合是 $$$c_1 \cdot a_1 + c_2 \cdot a_2 + \ldots + c_k \cdot a_k$$$ 形式的任意和,其中 $$$c_1, \ldots, \ldots, c_k$$$ 是整数(可以是零、正数或负)。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 100$$$),测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$),即集合的大小。第二行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^5$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^6$$$。
输出
在每个测试用例的第一行打印最大整数线性独立子集的大小。
在下一行中,以任意顺序打印一个此类子集。如果有多个有效子集,则打印其中任何一个。
示例
输入 #1
3 5 2 4 6 8 10 5 12 15 21 30 35 3 2 3 6
输出 #1
2 4 6 3 35 21 30 2 2 3
注意
在示例 1 中,$$$\{4, 6\}$$$ 是整数线性无关子集。可以证明不存在至少有$$$3$$$个元素的整数线性无关子集。
在示例 2 中,$$$\{35, 21, 30\}$$$ 是整数线性独立子集,因为任何两个元素的整数线性组合都不能创建第三个。不存在至少具有 $$$4$$$ 元素的整数线性独立子集。
在示例 3 中,$$$\{2, 3, 6\}$$$ 不是整数线性独立子集,因为 $$$6$$$ 可以写为 $$$6 \cdot 2 + (-2) \cdot 3$$$,它是 $$$\{2, 3\}$$$ 的整数线性组合。