Longest Divisible Subsequence

You are given an array of integers. Your task is to find the length of the longest subsequence such that for every two consecutive elements \(x_{i-1}\) and \(x_i\) in the subsequence, either \(x_i \bmod x_{i-1} = 0\) or \(x_{i-1} \bmod x_i = 0\) holds.

In other words, if the subsequence is \(a_1, a_2, \dots, a_k\), then for every \(i\) (\(2 \leq i \leq k\)) you must have either \[ a_i \bmod a_{i-1} = 0 \quad \text{or} \quad a_{i-1} \bmod a_i = 0. \]

For example, given the array [3, 6, 7, 18], one valid subsequence is [3, 6, 18] whose length is 3.

inputFormat

The input is given via standard input. The first line contains a single integer \(T\) (\(1 \leq T \leq 100\)) denoting the number of test cases. The subsequent lines describe each test case as follows:

• The first line of each test case contains an integer \(n\) (\(1 \leq n \leq 10^3\)) denoting the size of the array.
• The next line contains \(n\) space-separated integers representing the elements of the array.

It is guaranteed that the total number of elements in all test cases does not exceed \(10^4\).

outputFormat

For each test case, output a single integer on a new line representing the length of the longest subsequence that satisfies the condition.

## sample

1
1

1

</p>