Nasser's GCD Partners#12480
Asmaa is given an array of positive integers.
Her task is to find the maximum length of a subsequence such that for every element in the subsequence, there exists at least one other element in the subsequence with greater than .
In other words, in the chosen subsequence, no element should be isolated — each element must have at least one partner with whom it shares a common divisor greater than .
A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.
The first line contains a single integer (1 \le t \le 10^4) — the number of test cases.
The first line of each test case contains an integer (1 \le n \le 10^6) — the length of the array.
The second line contains integers a_1, a_2, \ldots, a_n (1 \le a_1, a_2, \ldots, a_n \le n) — the elements of the array.
It is guaranteed that the sum of all over all test cases does not exceed 10^6.
For each test case, output a single integer — the maximum length of a subsequence satisfying the condition.
Example 1
Subtask ( points) : (1 \le \sum n \le 100)
Subtask ( points) : (all a_i are primes)
Subtask ( points) : (1 \le \sum n \le 10000)
Subtask ( points) : No additional constraints.