该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

大白发明了他的数组美的标准。他称一个数组为美丽的，如果对于每一对不同的索$i,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$ 时不满足);

丑陋的数组惹恼了大白，所以他想从数组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$ 的元素.

输出

对于每个测试例子输出一个整数 — 使数组$a$变美丽需要移除的元素的最小值。

样例

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

2
0
1
0

提示

在第一个测试例子中，移除$7$和$14$将会使数组$a$变美丽。

在第二个测试例子中，数组$a$已经是美丽的。

在第三个测试例子中，移除$45$和$18$中的一个将会使数组$a$变美丽。

在第四个测试例子中，数组$a$已经是美丽的。