题目描述

你有一个大小为 $n$ 的整数数组 $a$。

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

花费一枚硬币，将任意一个元素加 1（需要至少一枚硬币才能执行）；

获得一枚硬币，将任意一个元素减 1。

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

1 所有元素都 不小于 2；

2 任意两个不同下标 $i \ne j$，有 $\gcd(a_i, a_j) = 1$。

如果数组长度小于 2，那么第 2 条自动成立。

我们称一个数组是 美丽的（beautiful），如果从初始状态（初始硬币数为 0）出发，经过上述操作后，可以变成一个 理想数组。

初始的数组不一定是美丽的。你可以选择删除其中任意数量的元素（包括全部删除，或不删除）。

请你求出：最少需要删除多少个元素，使得剩下的数组是美丽的。

PS：你必须先删除原始数组中任意数量的元素后才能进行操作。

输入格式

第一行是一个整数 $t$（$1 \le t \le 10^4$）——测试数据组数。

每组数据包含两行：

第一行一个整数 $n$（$1 \le n \le 4 \times 10^5$）——数组长度；

第二行 $n$ 个整数 $a_1, a_2, ..., a_n$（$2 \le a_i \le 10^9$）——数组元素。

保证所有测试用例中，$\sum n \le 4 \times 10^5$。

输出格式

每组测试输出一行，一个整数，表示最少需要删除的元素数目，使得剩余数组是美丽的。

样例

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]→[4,5,5]→[4,4,5]→[4,3,5]（最终得到 3 枚硬币）。在第二个例子中，你需要删除 2 个元素才能使数组变得完美。如果你保留元素 [2,3] 并删除其他元素，那么给定的数组已经是理想的（因此也是完美的）。在第三个例子中，你不需要删除任何元素，因为数组已经是理想的（因此也是完美的）。在第四个例子中，数组是完美的。它可以被转换成一个理想数组，如下所示：[2,100,2]→[2,99,2]→[2,99,3]→[2,98,3]→[2,97,3]（最终得到 2 枚硬币）。