奇异之美

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

称一个数组是美丽的，当且仅当对任意两个不同下标 $i\ne j$，$a_i$ 能被 $a_j$ 整除，或 $a_j$ 能被 $a_i$ 整除。

例如，$[2,14,42]$ 是美丽的，而 $[45,9,3,18]$ 不是美丽的，因为 $45$ 与 $18$ 互不整除。

给定数组 $a$，你可以删除若干元素。求至少删除多少个元素，才能使剩余数组变为美丽数组。

输入格式

第一行包含整数 $t$，表示测试用例数。

每个测试用例的第一行包含整数 $n$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数，表示最少删除的元素数。

样例输入 1

4
5
7 9 3 14 63
3
2 14 42
4
45 9 3 18
3
2 2 8

样例输出 1

2
0
1
0

数据范围

对于所有测试数据：

• $1\le t\le 10$；
• $1\le n\le 2\times 10^5$；
• $1\le a_i\le 2\times 10^5$。

每个测试点独立计分；同一子任务内各测试点等分。