优美的最长上升子序列

题目描述

多组数据。

每组给定一个长度为 $N$ 的数组 $\{A\}$。请从中选出一个递增的子序列，并要求所选择元素的下标（从 $1$ 开始）满足

其中 $a\mid b$ 表示 $a$ 整除 $b$（$a$ 是 $b$ 的约数）。求能选出的子序列的最大长度。

输入格式

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

每组数据包含两行：第一行一个整数 $N$；随后一行 $N$ 个整数，表示数组 $\{A\}$。

输出格式

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

样例输入

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$。

数据范围

• $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$