A - Orac and Models（最长上升子序列——加强版）

There are nn models in the shop numbered from 11 to nn, with sizes s_1, s_2, \ldots, s_ns1​,s2​,…,sn​.

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_jij​ and i_{j+1}ij+1​ (note that i_j < i_{j+1}ij​<ij+1​, because Orac arranged them properly), i_{j+1}ij+1​ is divisible by i_jij​ and s_{i_j} < s_{i_{j+1}}sij​​<sij+1​​.

For example, for 66 models with sizes \{3, 6, 7, 7, 7, 7\}{3,6,7,7,7,7}, he can buy models with indices 11, 22, and 66, 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.

Input

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

Each query contains two lines. The first line contains one integer n\ (1\le n\le 100\,000)n (1≤n≤100000): the number of models in the shop, and the second line contains nn integers s_1,\dots,s_n\ (1\le s_i\le 10^9)s1​,…,sn​ (1≤si​≤109): the sizes of models.

It is guaranteed that the total sum of nn is at most 100\,000100000.

Output

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

Sample 1

Inputcopy	Outputcopy
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

Note

In the first query, for example, Orac can buy models with indices 22 and 44, the arrangement will be beautiful because 44 is divisible by 22 and 66 is more than 33. 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 11, 33, and 66. 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.、、

题目翻译：

给出n个数的值，求出满足下标j整除i并且a[j]>a[i]的最多个数（j>i)

#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<cstdlib>using namespace std;
const int N = 1e5 + 10;int a[N],b[N];//DP:b[i]表示以i结尾的子序列的长度int main()
{int t; cin >> t;while (t--){int n; cin >> n;for (int i = 1; i <= n; i++) cin >> a[i]; //读入数据for (int i = 1; i <= n; i++) b[i] = 1;for (int i = 1; i <= n; i++)for (int j = 2 * i; j <= n; j += i) //满足条件1：j是i的倍数，j可以整除iif (a[i] < a[j]) b[j] = max(b[j], b[i] + 1); //满足条件2：a[j]>a[i]//DP：以选不选第j个数作为比较，求最大的那个//选j：长度为j的上一个数i加1，即b[i]+1；//不选j：即b[j]int ans = -INT_MAX;for (int i = 1; i <= n; i++) ans = max(ans, b[i]);cout << ans << endl;}}