← 返回题目列表

Codeforces · 1475/G

G. 奇怪的美

中文机器翻译题面 查看原题

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$$$ 很漂亮。