给您一个无向图,其中 $$$n$$$ 个顶点的索引从 $$$1$$$ 到 $$$n$$$,其中顶点 $$$i$$$ 分配了一个值 $$$a_i$$$,并且所有值 $$$a_i$$$ 都不同。如果 $$$a_u$$$ 整除 $$$a_v$$$ 或 $$$a_v$$$ 整除 $$$a_u$$$,则两个顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。
找到要删除的最小顶点数,使得剩余图是二分图,当您删除一个顶点时,您将删除与其关联的所有边。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5\cdot10^4$$$) — 图中的顶点数。
每个测试用例的第二行包含 $$$n$$$ 个整数,其中第 $$$i$$$ 是分配给第 $$$i$$$ 个顶点的值 $$$a_i$$$ ($$$1 \le a_i \le 5\cdot10^4$$$),所有值 $$$a_i$$$ 都不同。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot10^4$$$。
输出
对于每个测试用例,打印一个整数 - 要删除的最小顶点数,以便剩余图是二分图。
示例
输入 #1
4 4 8 4 2 1 4 30 2 3 5 5 12 4 6 2 3 10 85 195 5 39 3 13 266 154 14 2
输出 #1
2 0 1 2
注意
在第一个测试用例中,如果我们删除值为 $$$1$$$ 和 $$$2$$$ 的顶点,我们将获得一个二分图,所以答案是 $$$2$$$,不可能删除少于 $$$2$$$ 的顶点并仍然获得二分图。
BeforeAfter测试用例#1
在第二个测试用例中,我们不必删除任何顶点,因为图已经是二分图,所以答案是 $$$0$$$。
BeforeAfter测试用例#2
在第三个测试用例中,我们只需删除值为 $$$12$$$ 的顶点,因此答案是 $$$1$$$。
BeforeAfter测试用例#3
在第四个测试用例中,我们删除了值为 $$$2$$$ 和 $$$195$$$ 的顶点,所以答案是 $$$2$$$。
BeforeAfter测试用例#4