{"trustable":false,"sections":[{"title":"Description","value":{"format":"MD","content":"\n\u003e Now listen here Mikey.\n\u003e\n\u003e Brody and Chad will host the most epic party this weekend.\n\u003e\n\u003e All the popular people are coming. \n\u003e\n\u003e But guess who\u0027s not coming?\n\u003e\n\u003e Youuuuuu!\n\n![YOU](https://s2.loli.net/2023/07/13/KDSYkfjIE37lJ16.jpg)\n\nACM协会的部长们经常在群里组饭局,但总有人~~被孤立~~无法到场。\n\n给部长们分别设定一个互不相同的编号。一组可怜的部长被孤立,当且仅当这组人中不存在任何一个人的编号是这个人编号的质数倍。我们不妨称这个集合为孤立集。\n\n$a$ 是 $b$ 的质数倍当且仅当 $a\u003db \\times k (k为质数)$。例如:10 是 2 的质数倍,因为$10\u003d2\\times 5$,显然 5 为质数;集合 ``2,8,32`` 为孤立集,但 ``2,4,6`` 和 ``3,6,9`` 不是孤立集。\n\n现在给出部长的编号,求最大孤立集的人数。"}},{"title":"Input","value":{"format":"MD","content":"第一行是一个整数 $T (1\\le T\\le 20)$,表示数据组数。\n\n每组数据第一行为一个整数 $N(1\\le N\\le 40000)$,表示部长人数。接下来一行,有 $N$ 个整数 $A_i(1\\le A_i\\le 500000)$,表示部长们的编号。"}},{"title":"Output","value":{"format":"MD","content":"每组数据输出一个数,对于第i组,输出 `Case i: x`,$x$ 表示最大孤立集的人数。"}},{"title":"Sample","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\n"}},{"title":"Note","value":{"format":"MD","content":"数据量可能很大,请使用较为高效的输入输出方式。"}}]}