B. Orac 和模型
每次测试时间限制：$3$ 秒
内存限制：$256$ 兆字节

商店里有 $n$ 个模型，编号从 $1$ 到 $n$，尺寸分别为 $s_1, s_2, \dots, s_n$。

Orac 会购买其中一些模型，并按编号递增的顺序排列（即按下标顺序，而不是按尺寸）。

Orac 认为，如果对于任意两个相邻的模型（下标分别为 $i_j$ 和 $i_{j+1}$，满足 $i_j < i_{j+1}$），有 $i_{j+1}$ 能被 $i_j$ 整除，且 $s_{i_j} < s_{i_{j+1}}$，那么这样得到的排列是优美的。

例如，对于 $6$ 个模型，尺寸为 $\{3,6,7,7,7,7\}$，他可以购买下标为 $1$、$2$ 和 $6$ 的模型，得到的排列是优美的。此外，只包含一个模型的排列也被认为是优美的。

Orac 想知道他最多能购买多少个模型，并且他可能会多次询问这个问题。

输入
第一行包含一个整数 $t$（$1 \le t \le 100$）——查询的数量。
每个查询包含两行：

• 第一行包含一个整数 $n$（$1 \le n \le 10^5$）——商店中模型的数量。
• 第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \le s_i \le 10^9$）——模型的尺寸。

保证所有查询的 $n$ 之和不超过 $10^5$。

输出
输出 $t$ 行，第 $i$ 行应包含第 $i$ 个查询中 Orac 能购买的模型的最大数量。

示例

输入

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

输出

2
3
1
1

说明

• 在第一个查询中，例如 Orac 可以购买下标为 $2$ 和 $4$ 的模型，因为 $4$ 能被 $2$ 整除，且 $6 > 3$。通过枚举可知，不存在超过两个模型的优美排列。
• 在第二个查询中，Orac 可以购买下标为 $1$、$3$ 和 $6$ 的模型。通过枚举可知，不存在超过三个模型的优美排列。
• 在第三个查询中，不存在超过一个模型的优美排列。B. Orac 和模型
  每次测试时间限制：$3$ 秒
  内存限制：$256$ 兆字节

商店里有 $n$ 个模型，编号从 $1$ 到 $n$，尺寸分别为 $s_1, s_2, \dots, s_n$。

Orac 会购买其中一些模型，并按编号递增的顺序排列（即按下标顺序，而不是按尺寸）。

Orac 认为，如果对于任意两个相邻的模型（下标分别为 $i_j$ 和 $i_{j+1}$，满足 $i_j < i_{j+1}$），有 $i_{j+1}$ 能被 $i_j$ 整除，且 $s_{i_j} < s_{i_{j+1}}$，那么这样得到的排列是优美的。

例如，对于 $6$ 个模型，尺寸为 $\{3,6,7,7,7,7\}$，他可以购买下标为 $1$、$2$ 和 $6$ 的模型，得到的排列是优美的。此外，只包含一个模型的排列也被认为是优美的。

Orac 想知道他最多能购买多少个模型，并且他可能会多次询问这个问题。

输入
第一行包含一个整数 $t$（$1 \le t \le 100$）——查询的数量。
每个查询包含两行：

• 第一行包含一个整数 $n$（$1 \le n \le 10^5$）——商店中模型的数量。
• 第二行包含 $n$ 个整数 $s_1, s_2, \dots, s_n$（$1 \le s_i \le 10^9$）——模型的尺寸。

保证所有查询的 $n$ 之和不超过 $10^5$。

输出
输出 $t$ 行，第 $i$ 行应包含第 $i$ 个查询中 Orac 能购买的模型的最大数量。

示例

输入

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

输出

2
3
1
1

说明

• 在第一个查询中，例如 Orac 可以购买下标为 $2$ 和 $4$ 的模型，因为 $4$ 能被 $2$ 整除，且 $6 > 3$。通过枚举可知，不存在超过两个模型的优美排列。
• 在第二个查询中，Orac 可以购买下标为 $1$、$3$ 和 $6$ 的模型。通过枚举可知，不存在超过三个模型的优美排列。
• 在第三个查询中，不存在超过一个模型的优美排列。