D-小L的数列_牛客IOI周赛23-普及组

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

小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表示测试点的个数。
对于每一个测试点有两行：
第一行一个正整数 ，表示优秀的数的个数
第二行  个整数 ，表示小 L 称为优秀的数，保证  两两不相同。

输出描述:

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

示例1

输入

复制

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

输出

复制

4
4

说明

对于第一个测试点来说，一个最长的好的序列可以是 [2, 4, 6, 9]，长度为 4 。容易看出没有更长的好的序列。
对于第二个测试点来说，一个最长的好的序列可以是[3, 6, 8, 10]，长度为 4 。容易看出没有更长的好的序列。
对于  的数据，满足 。
对于  的数据，满足 。
另有  的数据，满足。
对于  的数据，满足  两两不同。