Problem Description

You are given a constant $m$ and a sequence $a$ of length $n$.

Define one "common divisor transformation" as follows:
First set $b_i \leftarrow a_i + \gcd(m, a_1, ..., a_i)$, and finally set $a_i \leftarrow b_i$. (Note that you must compute all $b_i$ first and then assign them to $a_i$ one by one, rather than computing and assigning at the same time.)

Find the minimum number of "common divisor transformations" needed so that $\forall i \in [1,n]$, $m \mid a_i$.

It can be proven that a solution always exists.

Input Format

The first line contains two integers $n$ and $m$, representing the length of the sequence and the given constant.
The next line contains $n$ integers, where the $i$-th integer is $a_i$.

Output Format

Output one integer in a single line, representing the answer.

5 5
5 4 3 2 1

4

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

263

Hint

[Sample Explanation 1]

After the first "common divisor transformation", the sequence becomes $10, 5, 4, 3, 2$.
After the second "common divisor transformation", the sequence becomes $15, 10, 5, 4, 3$.
After the third "common divisor transformation", the sequence becomes $20, 15, 10, 5, 4$.
After the fourth "common divisor transformation", the sequence becomes $25, 20, 15, 10, 5$.
So the answer is $4$.

[Constraints]
This problem uses bundled testdata.

• Subtask 1 (5 pts): $m = 1$.
• Subtask 2 (10 pts): $m = 2$.
• Subtask 3 (10 pts): $n = 1$ and $m \le 500$.
• Subtask 4 (15 pts): $n = 1$.
• Subtask 5 (10 pts): $n \le 5000$.
• Subtask 6 (20 pts): $n \le 5 \times 10^4$.
• Subtask 7 (10 pts): $m, a_i \le 10^9$.
• Subtask 8 (20 pts): No special constraints.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le m \le 10^{14}$, $1 \le a_i \le 10^{18}$. It is guaranteed that the answer fits in long long.

Translated by ChatGPT 5