問題文

　正整数 $n$ に対し、$n$ が素数 $p$ で割り切れる回数を $v_p(n)$ と表します。
より厳密には、正整数 $n$ について、非負整数 $k$ 及び $m\not\equiv 0\mod{p}$ である整数 $m$ の組で、$n=p^km$ が成り立つものが一意的に存在するので、$v_p(n)=k$ と定めます。

素数 $P$ と、全ての値が相異なる長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
$$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}v_P(|A_i-A_j|)$$
を求めてください。

入力

$N$ $P$
$A_1$ $A_2$ $\dots$ $A_N$

• $2 \leq N \leq 10^5$
• $2 \leq P \le 10^9$
• $P$ は素数
• $1 \leq A_i \le 10^9$
• $i\neq j$ ならば $A_i\neq A_j$
• 入力はすべて整数

出力

最後に改行してください。

サンプル

3 2
1 3 5

4

5 5
5 55 555 5555 55555

30

8 3
7023 2800 6599 9703 543 4221 1307 6572

18