HandsOn $3$: LIGCD

You are given an array A which consists of $N$ integers.

Find the length of the longest nondecreasing subsequence of A such that the GCD of all numbers in that sequence is greater than $1.$

Note:

A subsequence is a sequence that can be derived from another sequence by removing zero or more elements, without changing the order of the elements.

Input Format

The first line contains an integer, $N,$ denoting the number of elements in $A.$

Each line $i$ of the $N$ subsequent lines $($where $0i$