CF2104D.Array and GCD

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

你可以执行以下操作任意次数（包括零次）：

• 支付 1 枚硬币并将数组中的任意一个元素增加 $1$（执行此操作时你至少需要有 1 枚硬币）；
• 获得 1 枚硬币并将数组中的任意一个元素减少 $1$。

我们称一个数组是理想的，当且仅当满足以下两个条件：

1. 数组中的每个元素都至少为 $2$；
2. 对于任意两个不同的下标 $i$ 和 $j$（$1 \le i, j \le n$；$i \ne j$），$a_i$ 和 $a_j$ 的最大公约数（GCD）等于 $1$。如果数组元素少于 2 个，则此条件自动满足。

我们称一个数组是美丽的，如果可以通过上述操作将其转换为理想数组，且初始时你没有硬币。如果数组已经是理想的，那么它也是美丽的。

给定的数组不一定是美丽或理想的。你可以从中删除任意数量的元素（包括删除整个数组或不删除任何元素）。你的任务是计算为了使数组变得美丽，最少需要删除多少个元素（可以是零个）。

第一行包含一个整数 $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$。

对于每个测试用例，输出一个整数——为了使数组变得美丽，最少需要删除的元素数量（可以是零个）。

在第一个样例中，你不需要删除任何元素，因为数组已经是美丽的。可以通过以下操作将其转换为理想数组：$[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 枚硬币）。

翻译由 DeepSeek V3 完成