問題文

素数 $P$ と、長さ $N$ の数列 $A$ があります。はじめ $1$ で初期化されている変数 $x$ に対して、$x$ が $M$ 以下である限り以下の操作を繰り返します。

• もし $x$ が $P$ で割り切れるなら、$x$ を $P$ で割る。
• そうでないとき、 $1≤i≤N$ を満たす整数 $i$ を選び、$x$ に $A_i$ を掛ける。

操作回数が最小になるように操作をしたとき、合計で何回操作をすることになりますか？

ただし、どのように要素を選んでも操作が無限に繰り返される場合は $-1$ を出力してください。

入力

$N\ M\ P$
$A_1\ A_2\ ...\ A_N$

• $1≤N≤2×10^5$
• $1≤M,P≤10^9$
• $1≤A_i≤10^9$
• $P$ は素数
• 入力は全て整数

出力

操作が有限回で終わる場合操作回数の最小値を、終わらない場合 $-1$ を出力してください。
最後に改行してください。

サンプル

3 5 2
4 2 3

2

3 400 2
2 256 128

-1

8 29019 59
59 13021 392 192 392 12 293 40

2