{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"一组整数如果其中没有一个是另一个成员的素数倍数,则称为素数独立。如果一个整数 **a** 被另一个整数 **b** 的素数倍数,则称整数 **a** 是整数 **b** 的 **素数倍数**,即\n\n**a \u003d b x k** (其中 **k** 是一个素数 [1])\n\n因此,**6** 是 **2** 的素数倍数,但 **8** 不是。例如,**{2, 8, 17}** 是素数独立的,但 **{2, 8, 16}** 或 **{3, 6}** 不是。\n\n现在,给定一组不同的正整数,计算最大的素数独立子集。"}},{"title":"输入","value":{"format":"MD","content":"输入以一个整数 **T (\u0026le; 20)** 开始,表示测试用例的数量。\n\n每个测试用例以一个整数 **N (1 \u0026le; N \u0026le; 40000)** 开始,表示集合的大小。下一行包含 **N** 个整数,用一个空格分隔。这 **N** 个整数都是不同的,且在 **1** 到 **500000** 之间(包括边界值)。"}},{"title":"输出","value":{"format":"MD","content":"对于每个测试用例,输出案例编号和最大素数独立子集的大小。"}},{"title":"示例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n5\n2 4 8 16 32\n5\n2 3 4 6 9\n3\n1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 3\nCase 2: 3\nCase 3: 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"MD","content":"1. 如果一个整数能被两个不同的整数整除,则称其为素数。前几个素数是 **2, 3, 5, 7, 11, 13, ...**\n2. 数据集很大,请使用更快的I/O方法。"}}]}