問題文

長さNNの数列AAが与えられます.数列AAの空でない部分列で,全要素の最大公約数がMMであるもののうち最長のものの長さを求めてください.

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

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

部分列とは

数列AAの部分列とは,AAから00個以上の要素を取り除いた後,残りの数字を元の順序で並べて得られる数列のことです.

制約

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

入力

N MN\ M
A1ANA_1 \dots A_N

出力

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

サンプル

入力例1
5 10
120 50 40 92 30
出力例1
4

gcd(120,50,40,30)=10\gcd(120, 50, 40, 30) = 10であり,長さ55(以上)の部分列で要素の最大公約数が1010となるようなものはないため,答えは44です.

入力例2
5 10
120 50 40 90 30
出力例2
5

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

入力例3
5 10
120 80 40 60 520
出力例3
-1

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

Submit


Go (1.21)