Longest Coprime Subsequence

Given an array of integers, find the length of the longest subsequence such that every pair of consecutive elements in the subsequence are coprime. In other words, for any two consecutive numbers \(a\) and \(b\) in the subsequence, it must hold that \(\gcd(a, b) = 1\).

A subsequence is obtained by deleting zero or more elements from the array without changing the order of the remaining elements.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case consists of two lines:

1. The first line contains an integer \(N\), the number of elements in the array.
2. The second line contains \(N\) space-separated integers representing the array.

outputFormat

For each test case, output the length of the longest coprime subsequence on a separate line.

## sample

2
5
2 3 5 7 11
4
4 6 8 10

5
1

</p>