[BJWC2010] 取数游戏

题目描述

小 C 刚学了辗转相除法,正不亦乐乎,这小 P 又出来捣乱,给小 C 留了个 难题。 给 $N$ 个数,用 $a_1,a_2, \cdots ,a_n$来表示。现在小 P 让小 C 依次取数,第一个数可以 随意取。假使目前取得 $a_j$,下一个数取$a_k(k>j)$,则$a_k$必须满足$\mathrm{gcd}(a_j,a_k)≥L$。 到底要取多少个数呢?自然是越多越好! 不用多说,这不仅是给小 C 的难题,也是给你的难题。

输入输出格式

输入格式


第一行包含两个数$N$ 和 $L$。 接下来一行,有 $N$ 个数用空格隔开,依次是 $a_1,a_2,\cdots ,a_n$。

输出格式


仅包含一行一个数,表示按上述取法,最多可以取的数的个数。

输入输出样例

输入样例 #1

5 6 
7 16 9 24 6

输出样例 #1

3

说明

### 样例解释 选取 $3$个数$16,24,6$。$\mathrm{gcd}(16,24)=8$,$\mathrm{gcd}(6,24)=6$。 ### 数据范围 30% 的数据$N≤1000$; 100% 的数据 $N≤50 000,2≤L≤a_i≤1 000 000$。