Beautiful Longest Increasing Subsequence

Problem Description

There are multiple test cases.

For each case you are given an array $\{A\}$ of length $N$. Choose an increasing subsequence from it whose indices (1-based) satisfy

where $a\mid b$ means $a$ divides $b$ ($a$ is a divisor of $b$). Find the maximum possible length of such a subsequence.

Input Format

The first line contains an integer $T$, the number of test cases that follow.

Each test case contains two lines: the first line contains an integer $N$; the next line contains $N$ integers, representing the array $\{A\}$.

Output Format

For each test case, output one integer on a line, the length of the longest "beautiful" increasing subsequence that can be chosen.

Sample Input

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

Sample Output

3
1
4
1

Sample Explanation

• In the first case, a valid beautiful LIS is $\{A_1, A_2, A_4\} = \{1, 4, 7\}$.
• In the third case, we may choose $\{A_1, A_2, A_4, A_8\} = \{1, 2, 4, 8\}$.
• In the fourth case, the longest beautiful LIS has length $1$.

Constraints

• $1\le T\le 100$
• $1\le N\le 10^6$, and $\sum_{i=1}^{T} N_i\le 10^6$
• $1\le A_i\le 10^9$