【题目描述】

​ 小$L$喜欢数和数列。小$L$称$a_1...a_n$这些数为好的。小$L$称一个序列$b_1...b_m$为好的当且仅当：

​ $1.$对于任意的 $i$$(1 \leq i < m)$，满足 $b_i < b_{i+1}$。

​ $2$.对于任意的 $i$$(1 \leq i < m)$，满足 $gcd(b_i,b_{i+1})>1$。其中，$gcd(x,y)$为$x$和$y$的最大公因数，即最小的$d$，满足：$d|x且d|y$。

​ $3.$对于任意的 $i$$(1 \leq i \leq m)$，$b_i$这个数是好的。

​ 现在，小$L$想知道最长的能称为好的的序列的长度是多少，容易证明这个长度是有穷的。

【输入格式】

​ 有多组测试点，输入第一行一个数$T$表示测试点的个数。

​ 对于每一个测试点有两行：

​ 第一行一个正整数$n$，表示好的的数的个数

​ 第二行$n$个整数$a_1...a_n$，表示小$L$称为好的的数，保证$a_i$两两不相同。

【输出格式】

​ 输出共$T$行，每一行为一个测试点的答案，即最长的好的序列的长度。

【样例输入1】

2
5
4 6 3 2 9
9
10 2 5 3 6 9 7 8 1

【样例输出1】

4
4

【样例解释】

​ 对于第一个测试点来说，一个最长的好的序列可以是$[2,4,6,9]$，长度为$4$。容易看出没有更长的好的序列。

​ 对于第二个测试点来说，一个最长的好的序列可以是$[3,6,8,10]$，长度为$4$。容易看出没有更长的好的序列。

【样例2】

​ 见下发文件。

【数据范围】

​ 对于 $30\%$ 的数据，满足 $n,a_i \leq 10$。

​ 对于 $60\%$ 的数据，满足 $n,a_i \leq 1000$。

​ 另有 $20\%$ 的数据，满足$n \leq 1000$。

​ 对于 $100\%$ 的数据，满足 $2 \leq n,a_i \leq 100000,T \leq 5,a_i两两不同$。

时间限制：1s

空间限制：512MB