自时光中凝取的稀薄力量。正是所有微不足道的刹那，编织成了壮绝的命运。
「他凝视着那轮空洞，它犹如在万物终末时高悬的漆黑太阳，又像是一张解答一切疑问的口——那张口说道：███ █ ███ ██ 这答案无法以任何人类的语言诠释，却能被所有人听懂。 」

有 n 个正整数构成的序列 a[1],a[2],...,a[n] ，你需要从中选出若干数，使得被选出的数的最小公倍数不在被选出的数中，求最多可以选择多少个数。

第一行包含一个正整数 T (1≤T≤2000) ，表示数据组数。
每组数据第一行包含一个正整数n (1≤n≤2000) ，表示序列大小。
每组数据第二行包含 n 个正整数 a[1],a[2],...,a[n] (1≤a[i]≤10^9) ，表示序列中的数。
保证所有 n 之和不超过 2000 。

每组数据输出一行包含一个整数，表示答案。

6
5
1 2 4 8 16
6
3 2 10 20 60 1
7
2 3 4 6 12 100003 1200036
9
2 42 7 3 6 7 7 1 6
8
4 99 57 179 10203 2 11 40812
1
1

0
4
4
5
8
0

样例解释：
在第一组数据中，无法选择任何数，因此答案是 0 。
在第二组数据中，我们可以选取 {3,2,10,1} ，它的LCM等于 30  ，它不包含在被选取的数中。
在第三组数据中，我们可以 {2,3,6,100003} ，它的LCM等于 600018 ，它不包含在被选取的数中。