小苯的整除序列

题号：NC316017
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 给定一个长度为 $n$ 的正整数数组 $a$ 。
$\hspace{15pt}$ 你需要从中选择一个尽可能长的子序列 $b_1, b_2, \dots, b_k$ ，要求满足：
$\hspace{23pt}\bullet\ b_i \bmod i = 0 \quad (1 \leqq i \leqq k)$
$\hspace{15pt}$ 也就是说，子序列中的第 $1$ 个数必须能被 $1$ 整除，第 $2$ 个数必须能被 $2$ 整除，第 $3$ 个数必须能被 $3$ 整除，依此类推。

$\hspace{15pt}$ 子序列中的元素在原数组中的相对顺序必须保持不变，但不要求连续。
$\hspace{15pt}$ 你的任务就是求出满足条件的最长子序列长度。

输入描述:

每个测试文件包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行一个整数 。
第二行  个整数 。
保证所有测试数据中  的总和不超过 。

输出描述:

对于每组数据，输出一行一个整数，表示满足条件的最长子序列长度。

示例1

输入

复制

3
6
1 4 2 9 6 12
3
2 2 2
3
5 7 11

输出

复制

4
2
1

说明

对于第一组数据，一种最优方案为选择子序列 。

  能被  整除
  能被  整除
  能被  整除
  能被  整除
因此答案为 。

对于第二组数据，可以选择前两项组成子序列 。
其中第一个  能被  整除，第二个  能被  整除，因此答案为 。

对于第三组数据，任意一个数都可以单独作为长度为  的合法子序列，但无法组成长度为  的合法子序列，因此答案为 。