Polycarp 在街上发现了一个由 $$$n$$$ 元素组成的数组 $$$a$$$。
波利卡普发明了他的数组美感标准。如果每对不同的索引 $$$i \ne j$$$ 必须至少满足以下条件之一,他称数组 $$$a$$$ 漂亮:
- $$$a_i$$$ 可以被 $$$a_j$$$ 整除;
- 或 $$$a_j$$$ 可以被 $$$a_i$$$ 整除。
例如,如果:
- $$$n=5$$$ 和 $$$a=[7, 9, 3, 14, 63]$$$,则 $$$a$$$ 数组并不美观(对于 $$$i=4$$$ 和 $$$j=2$$$,以上条件都不满足);
- $$$n=3$$$ 和 $$$a=[2, 14, 42]$$$,那么 $$$a$$$ 数组就很漂亮;
- $$$n=4$$$ 和 $$$a=[45, 9, 3, 18]$$$,那么 $$$a$$$ 数组并不漂亮(对于 $$$i=1$$$ 和 $$$j=4$$$ 上述条件都不满足);
丑陋的数组让 Polycarp 很不高兴,所以他想从数组 $$$a$$$ 中删除一些元素,使其变得漂亮。帮助 Polycarp 确定要删除的最小元素数,以使数组 $$$a$$$ 更美观。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 数字 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的元素。
输出
对于每个测试用例,输出一个整数——为了使数组 $$$a$$$ 漂亮而必须删除的最小元素数。
示例
输入 #1
4 5 7 9 3 14 63 3 2 14 42 4 45 9 3 18 3 2 2 8
输出 #1
2 0 1 0
注意
在第一个测试用例中,删除 $$$7$$$ 和 $$$14$$$ 将使数组 $$$a$$$ 变得漂亮。
在第二个测试用例中,数组 $$$a$$$ 已经很漂亮了。
在第三个测试用例中,删除元素 $$$45$$$ 或 $$$18$$$ 之一将使数组 $$$a$$$ 变得漂亮。
在第四个测试用例中,数组 $$$a$$$ 很漂亮。