Maximize Sequence Picks with GCD Constraint

You are given a sequence of N positive integers, denoted as \(a_1, a_2, \ldots, a_N\). You have to pick a subsequence from this array subject to the following condition:

• You can start by picking any element from the sequence.
• If the last picked element is \(a_j\), then the next picked element \(a_k\) (with \(k > j\)) must satisfy \(\gcd(a_j,a_k) \ge L\), where \(L\) is a given threshold.

Your task is to determine the maximum number of elements you can pick under the above conditions.

Note: \(\gcd(x,y)\) denotes the greatest common divisor of \(x\) and \(y\), and all formulas are in \(\LaTeX\) format.

inputFormat

The input consists of two lines:

• The first line contains two integers \(N\) and \(L\), where \(N\) is the number of elements and \(L\) is the GCD threshold.
• The second line contains \(N\) positive integers representing the sequence \(a_1, a_2, \ldots, a_N\).

outputFormat

Output a single integer representing the maximum number of elements you can pick following the given conditions.

sample

5 2
4 8 3 6 9

4