给定一个整数数组 $$$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$$$ 中删除的最小元素数(可能为零)才能使其 美丽.
示例
输入复制
535 5 542 3 2 41332 100 252 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$$$ 硬币)。