B. k-冲突数对
time limit per test
2 seconds
memory limit per test
64 megabytes
input
standard input
output
standard output

我们遥望 却不在同一片光年下燃烧 如同赫利孔山的清泉与尘世的井 数字在深潭底静默 保持各自的晶莹

没有两颗星会被相同的引力弯曲轨道 当猎户座腰带亮起 天狼便退入寂寥 这是银河的契约：永不相交的辉芒

所有试图靠近的轨迹都将坠入虚无 像被风驱散的种子 各自寻找孤独的土壤 唯有保持距离的星座 才能通过时间的长廊

秋夜如此辽阔 足够容纳每盏独立的灯 天鹅飞越天河时 翅膀从不触碰波浪 正如我们怀抱完整的光 在黑暗中平行穿行

请注意本题特殊的时空限制，并使用较快的读入方式。

定义 "k-冲突数对" 为满足 的数对 (x, y) ，其中 表示 x 和 y 的最大公因数。

现在给定一个长度为 n 的数组 [a1, a2, ..., an] ，保证所有 ai 两两不同。

对于 1 ≤ l ≤ r ≤ n ，如果 不存在 两个（可能相同的）下标 l ≤ i, j ≤ r ，满足 (ai, aj) 为 "k-冲突数对" ，则称子数组 [al, al + 1, ..., ar] 是合法的。特殊地，空数组 [] 也是 a 的子数组。

你需要求出数组 a 的 最长 合法子数组的长度。

Input

第一行 2 个整数 n 和 k（1 ≤ n, k ≤ 1081080）。

第二行 n 个整数 a1, a2, ..., an（1 ≤ ai ≤ 10810802，且所有 ai 两两不同）。

Output

输出一个整数，表示最长合法子数组的长度。

Examples
Input
1 1
1
Output
0
Input
4 4
2 3 4 5
Output
1
Input
7 8
4 3 6 7 2 5 1
Output
3
Input
5 114514
11 45 14 1919 810
Output
5
Note

在第一个样例中，(a1, a1) 为冲突数对，最长合法连续子数组为 [] ，长度为 0 。

在第二个样例中，最长合法连续子数组为 [2] 、[3] 和 [5] ，长度为 1 。

在第三个样例中，最长合法连续子数组为 [3, 6, 7] 和 [2, 5, 1] ，长度为 3 。