← 返回题目列表

Codeforces · 2104/D

D. 数组和 GCD

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

给定一个整数数组 $$$a$$$,大小为 $$$n$$$。

您可以执行以下操作任意次数(可能为零):

  • 支付一枚硬币,并将数组的任意元素增加 $$$1$$$(您必须至少拥有 $$$1$$$ 硬币才能执行此操作);
  • 获得一枚硬币并将数组的任何元素减少 $$$1$$$。

假设一个数组是 理想 如果满足以下两个条件:

  • 数组的每个元素至少为$$$2$$$;
  • 对于每对索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$; $$$i \ne j$$$),$$$a_i$$$ 和 $$$a_j$$$ 的最大公约数 (GCD) 等于 $$$1$$$。如果数组的元素少于 $$$2$$$,则自动满足此条件。

假设一个数组是 美丽 如果你一开始没有金币,可以通过上述操作将其转化为理想数组。如果阵列已经很理想,那么它也很漂亮。

给定的数组不一定漂亮或理想。您可以从中删除任何元素(包括删除整个数组或根本不删除任何元素)。您的任务是计算必须从数组 $$$a$$$ 中删除的最小元素数(可能为零)才能使其成为 美丽.

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 4 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$2 \le a_i \le 10^9$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$4 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 您必须从数组 $$$a$$$ 中删除的最小元素数(可能为零)才能使其 美丽.

示例

输入
复制

5
3
5 5 5
4
2 3 2 4
1
3
3
2 100 2
5
2 4 2 11 2

输出
复制

0
2
0
0
1

注意

在第一个示例中,您不需要删除任何元素,因为数组已经很漂亮了。它可以转换为理想数组,如下所示: $$$[5, 5, 5] \rightarrow [4, 5, 5] \rightarrow [4, 4, 5] \rightarrow [4, 3, 5]$$$ (你最终会得到 $$$3$$$ 硬币)。

在第二个示例中,需要删除 $$$2$$$ 元素,以便数组变得漂亮。如果保留元素 $$$[2, 3]$$$ 并删除其他元素,则给定的数组已经是理想的(因此很漂亮)。

在第三个示例中,您不需要删除任何元素,因为数组已经是理想的(因此很漂亮)。

在第四个示例中,数组很漂亮。它可以转换为理想数组,如下所示: $$$[2, 100, 2] \rightarrow [2, 99, 2] \rightarrow [2, 99, 3] \rightarrow [2, 98, 3] \rightarrow [2, 97, 3]$$$ (你最终会得到 $$$2$$$ 硬币)。