Description

Xiao C has just learned the Euclidean algorithm and is enjoying it, but Xiao P comes to make trouble and leaves Xiao C with a hard problem. You are given $N$ numbers, denoted by $a_1, a_2, \cdots, a_n$. Now Xiao P asks Xiao C to pick numbers one by one in order. The first number can be chosen arbitrarily. Suppose the current number is $a_j$. To pick the next number $a_k$ with $k > j$, the number $a_k$ must satisfy $\mathrm{gcd}(a_j, a_k) \ge L$.

How many numbers should be picked? Naturally, as many as possible. Needless to say, this is not only a challenge for Xiao C, but also for you.

Input Format

The first line contains two numbers $N$ and $L$.
The second line contains $N$ numbers separated by spaces: $a_1, a_2, \cdots, a_n$.

Output Format

Output a single line with one number, the maximum count of numbers that can be picked according to the rule.

5 6 
7 16 9 24 6

3

Hint

Sample Explanation

Pick $3$ numbers: $16, 24, 6$. $\mathrm{gcd}(16, 24) = 8$, $\mathrm{gcd}(6, 24) = 6$.

Constraints

For 30% of the testdata, $N \le 1000$.
For 100% of the testdata, $N \le 50\,000$, $2 \le L \le a_i \le 1\,000\,000$.

Translated by ChatGPT 5