题目描述

给出一个常数 $m$ 和长度为 $n$ 的序列 $a$。

定义一次「公约数变换」为：
先令 $b_i\leftarrow a_i+\gcd(m,a_1,...,a_i)$，最后令 $a_i\leftarrow b_i$。（注意是先把每个 $b_i$ 都算出来再一一赋值，而不是边算边赋值）

请问最少做几次「公约数变换」使得 $\forall i \in[1,n]$，$m|a_i$。

可以证明一定有解。

输入格式

第一行两个整数 $n$ 和 $m$，表示序列长度和给出的常数。
接下来一行 $n$ 个整数，第 $i$ 个整数表示 $a_i$。

输出格式

一行一个整数，表示答案。

5 5
5 4 3 2 1

4

10 6154
1 3 6 4 2 5 7 8 1 2

263

提示

【样例解释 1】

第一次「公约数变换」后的序列为 $10,5,4,3,2$。
第二次「公约数变换」后的序列为 $15,10,5,4,3$。
第三次「公约数变换」后的序列为 $20,15,10,5,4$。
第四次「公约数变换」后的序列为 $25,20,15,10,5$。
可以得出答案为 $4$。

【数据范围】
本题采用捆绑测试。

• Subtask1（5pts）：$m=1$；
• Subtask2（10pts）：$m=2$；
• Subtask3（10pts）：$n=1$ 且 $m\le 500$；
• Subtask4（15pts）：$n=1$；
• Subtask5（10pts）：$n\le 5000$；
• Subtask6（20pts）：$n\le 5\times 10^4$；
• Subtask7（10pts）：$m,a_i\le 10^{9}$；
• Subtask8（20pts）：无特殊限制；

对于 $100\%$ 的数据，$1\le n\le 10^{5}$，$1\le m\le 10^{14}$，$1\le a_i\le 10^{18}$。保证答案在 long long 范围内。