题目内容

​ 小塔有一个长度为n的数组$[a1,a2,...,an]$。他定义一个中所有数的最小公倍数$lcm$不数组$x$是好的,当且仅当数存在于$x$中。例如，数组$[1,2,3,4]$是一个好数组，因为所有元素的$lcm=12$,而$12$不在数组中，所以它是一个好数组;而数组$[2,6,3]$不是好数组，因为所有元素的$lcm=6$,而$6$存在于数组中。 小塔希望从$a$中选择一个子序列，使得此子序列是好数组，并且他想知道子序列的最大长度。 如果数组$a$可以通过删除数组$b$中的若干(可能为零或全部)元素得到，则数组$a$是数组$b$的子序列。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T(1≤T≤100)$代表数据组数，每组测试数据描述如下: 第一行输入一个整数$n(1≤n≤2000)$代表数组中的元素数量。 第二行输入n个整数$a1,a2,...,an (1≤a_i≤10^9)$代表数组中的元素。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表可以选择的好子序列的最大长度。

样例1

输入

2
3
1 3 2
5
1 2 3 12 4

输出

3
4

说明

对于第一组测试数据，可以全选。 对于第二组测试数据，选择$[1,2,3,4]$，此时$lcm=12$，不在该子序列中，所以它是好的。