問題文

長さ$N$の数列$A$が与えられます．数列$A$の空でない部分列で，全要素の最大公約数が$M$であるもののうち最長のものの長さを求めてください．

ただし，そのような部分列が$1$つも存在しない場合は$-1$と出力してください．

また，数列の要素が$1$つの場合はその要素の値を最大公約数とします．つまり，任意の自然数$x$について，$\gcd(x) = x$です．

部分列とは

数列$A$の部分列とは，$A$から$0$個以上の要素を取り除いた後，残りの数字を元の順序で並べて得られる数列のことです．

制約

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i, M \leq 10^{18} \quad (1 \leq i \leq N)$
• 入力はすべて整数

入力

出力

数列$A$の部分列のうち，全要素の最大公約数が$M$であるのようなものの中で最長のものの長さを出力．ただし，そのような部分列が$1$つも存在しない場合は$-1$と出力してください．

サンプル

5 10
120 50 40 92 30

4

$\gcd(120, 50, 40, 30) = 10$であり，長さ$5$（以上）の部分列で要素の最大公約数が$10$となるようなものはないため，答えは$4$です．

5 10
120 50 40 90 30

5

$\gcd(120, 50, 40, 90, 30) = 10$です．

5 10
120 80 40 60 520

-1

どのように部分列を作っても，最大公約数を$10$にすることはできません．