CF1350B.Orac and Models

There are $n$ models in the shop numbered from $1$ to $n$, with sizes $s_1, s_2, \ldots, s_n$.

Orac will buy some of the models and will arrange them in the order of increasing numbers (i.e. indices, but not sizes).

Orac thinks that the obtained arrangement is beatiful, if for any two adjacent models with indices $i_j$ and $i_{j+1}$ (note that $i_j \lt i_{j+1}$, because Orac arranged them properly), $i_{j+1}$ is divisible by $i_j$ and $s_{i_j} \lt s_{i_{j+1}}$.

For example, for $6$ models with sizes ${3, 6, 7, 7, 7, 7}$, he can buy models with indices $1$, $2$, and $6$, and the obtained arrangement will be beautiful. Also, note that the arrangement with exactly one model is also considered beautiful.

Orac wants to know the maximum number of models that he can buy, and he may ask you these queries many times.

商店中有 $n$ 个编号为 $1$ 到 $n$ 的模型，其尺寸分别为 $s_1, s_2, \ldots, s_n$。

Orac 将购买其中若干模型，并按编号（即下标，而非尺寸）升序排列。

Orac 认为所得到的排列是优美的，当且仅当对任意两个相邻模型（其编号分别为 $i_j$ 和 $i_{j+1}$，注意由于 Orac 是按编号升序排列的，故必有 $i_j \lt i_{j+1}$），均满足：$i_{j+1}$ 能被 $i_j$ 整除，且 $s_{i_j} \lt s_{i_{j+1}}$。

例如，对于 $6$ 个尺寸为 ${3, 6, 7, 7, 7, 7}$ 的模型，Orac 可以购买编号为 $1$、$2$ 和 $6$ 的模型，所得排列即为优美的。另外请注意，仅含一个模型的排列也被视为优美的。

Orac 想知道他最多能购买多少个模型；他可能会多次向你提出此类查询。

The first line contains one integer $t\ (1 \le t\le 100)$: the number of queries.

Each query contains two lines. The first line contains one integer $n\ (1\le n\le 100\,000)$: the number of models in the shop, and the second line contains $n$ integers $s_1,\dots,s_n\ (1\le s_i\le 10^9)$: the sizes of models.

It is guaranteed that the total sum of $n$ is at most $100\,000$.

第一行包含一个整数 $t\ (1 \le t\le 100)$：查询次数。

每次查询包含两行。第一行包含一个整数 $n\ (1\le n\le 100\,000)$：商店中模型的数量；第二行包含 $n$ 个整数 $s_1,\dots,s_n\ (1\le s_i\le 10^9)$：各模型的尺寸。

保证所有查询中 $n$ 的总和不超过 $100\,000$。

Print $t$ lines, the $i$-th of them should contain the maximum number of models that Orac can buy for the $i$-th query.

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

In the first query, for example, Orac can buy models with indices $2$ and $4$, the arrangement will be beautiful because $4$ is divisible by $2$ and $6$ is more than $3$. By enumerating, we can easily find that there are no beautiful arrangements with more than two models.

In the second query, Orac can buy models with indices $1$, $3$, and $6$. By enumerating, we can easily find that there are no beautiful arrangements with more than three models.

In the third query, there are no beautiful arrangements with more than one model.

在第一次查询中，例如，Orac 可以购买索引为 $2$ 和 $4$ 的模型，该排列是优美的，因为 $4$ 能被 $2$ 整除，且 $6$ 大于 $3$。通过枚举，我们可以轻易发现：不存在包含超过两个模型的优美排列。

在第二次查询中，Orac 可以购买索引为 $1$、$3$ 和 $6$ 的模型。通过枚举，我们可以轻易发现：不存在包含超过三个模型的优美排列。

在第三次查询中，不存在包含超过一个模型的优美排列。