CF1475G.Strange Beauty

Polycarp found on the street an array $a$ of $n$ elements.

Polycarp invented his criterion for the beauty of an array. He calls an array $a$ beautiful if at least one of the following conditions must be met for each different pair of indices $i \ne j$:

• $a_i$ is divisible by $a_j$;
• or $a_j$ is divisible by $a_i$.

For example, if:

• $n=5$ and $a=[7, 9, 3, 14, 63]$, then the $a$ array is not beautiful (for $i=4$ and $j=2$, none of the conditions above is met);
• $n=3$ and $a=[2, 14, 42]$, then the $a$ array is beautiful;
• $n=4$ and $a=[45, 9, 3, 18]$, then the $a$ array is not beautiful (for $i=1$ and $j=4$ none of the conditions above is met);

Ugly arrays upset Polycarp, so he wants to remove some elements from the array $a$ so that it becomes beautiful. Help Polycarp determine the smallest number of elements to remove to make the array $a$ beautiful.

Polycarp 在街上发现了一个包含 $n$ 个元素的数组 $a$。

Polycarp 提出了他自己定义的数组“优美性”判据。他称一个数组 $a$ 是优美的，当且仅当对任意一对互异的下标 $i \ne j$，以下两个条件中至少有一个成立：

• $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$ 变为优美，所需删除的最少元素个数是多少？

The first line contains one integer $t$ ($1 \leq t \leq 10$) — the number of test cases. Then $t$ test cases follow.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ numbers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$) — elements of the array $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$ 的元素。

For each test case output one integer — the minimum number of elements that must be removed to make the array $a$ beautiful.

对于每个测试用例，输出一个整数——使数组 $a$ 变为“美丽”的所需删除的最少元素个数。

In the first test case, removing $7$ and $14$ will make array $a$ beautiful.

In the second test case, the array $a$ is already beautiful.

In the third test case, removing one of the elements $45$ or $18$ will make the array $a$ beautiful.

In the fourth test case, the array $a$ is beautiful.

在第一个测试用例中，移除 $7$ 和 $14$ 后，数组 $a$ 将变得优美。

在第二个测试用例中，数组 $a$ 本身已经是优美的。

在第三个测试用例中，移除元素 $45$ 或 $18$ 中的任意一个，即可使数组 $a$ 变得优美。

在第四个测试用例中，数组 $a$ 是优美的。