多组数据。

每组将给定一个数组。派派希望从中选择一个递增的子序列，越长越好。

但派派认为，这样选出来的子序列依然不够「优美」，形式化的讲，派派希望选择的下标（从 $1$ 开始）需要满足

$$i_1 \mid i_2 \mid i_3 \mid \cdots \mid i_k$$

其中 $a | b$ 表示整除， 即 $a$ 是 $b$ 的约数。

请你帮助派派完成任务吧！

注：子序列的含义不再赘述。

输入格式

第一行一个整数 $T$，表示接下来有 $T$ 组数据。

每组数据包含两行，第一行包含一个整数 $N$。

随后一行，包含 $N$ 个整数，表示原数组 $\{A\}$。

输出格式

对于每组数据，输出一行，包含一个数，表示能选出的「优美」的最长上升子序列长度。

数据规模

• $1 \le T \le 100$
• $1 \le N \le 10^6$,但保证 $\displaystyle\sum_{i = 1}^T N_i \le 10 ^ 6$
• $1 \le A_i \le 10^9$

样例输入

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

样例输出

3
1
4
1

解释：

对于第一组数据，能选择的「优美」最长上升子序列为 $\{A_1, A_2, A_4\} = \{1, 4, 7\}$。

对于第三组数组，选择 $\{A_1, A_2, A_4, A_8\} = \{1, 2, 4, 8\}$。

对于第四组数据，可选择的「优美」最长上升子序列长度为 $1$。