CF2034H Rayan vs. Rayaneh

为了赢得 Reyhaneh 的芳心，Rayan 宣称自己比计算机（波斯语中称为 Rayaneh）更强。为了验证他的说法，Reyhaneh 请教了 Khwarizmi。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, c_2, \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 中，集合 $\{4, 6\}$ 是一个整数线性无关的子集。可以证明不存在包含至少 3 个元素的整数线性无关子集。 例子 2 中，集合 $\{35, 21, 30\}$ 是一个整数线性无关的子集，因为任意两个元素的整数线性组合无法生成第三个元素。没有包含至少 4 个元素的整数线性无关子集。 例子 3 中，集合 $\{2, 3, 6\}$ 并不是一个整数线性无关的子集，因为 6 可以表示为 $ 6 \cdot 2 + (-2) \cdot 3 $，这是 $\{2, 3\}$ 的整数线性组合。 **本翻译由 AI 自动生成**