Longest Coprime Adjacent Subsequence

You are given an array of positive integers. Your task is to find the length of the longest subsequence (not necessarily contiguous) such that every pair of consecutive elements in this subsequence is coprime (i.e. for any two adjacent numbers \(a\) and \(b\), \(\gcd(a,b)=1\)).

For example, if the array is [6, 10, 15, 21, 35, 22], one valid subsequence is [10, 21, 22] because \(\gcd(10,21)=1\) and \(\gcd(21,22)=1\). Note that the subsequence must maintain the order of the original array.

Input Constraints: It is guaranteed that the input size is small enough to allow a solution with \(O(n^2)\) complexity.

Note: If there is only one element in the array, the answer is 1.

inputFormat

The first line of input contains a single integer \(n\) (1 \(\le\) n \(\le\) 1000) representing the number of elements in the array.

The second line contains \(n\) space-separated positive integers.

outputFormat

Output a single integer, the length of the longest subsequence where every pair of consecutive elements is coprime.

6
6 10 15 21 35 22

3