Make GCD M

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

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

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

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

• 入力はすべて整数

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

5 10
120 50 40 92 30

4

であり，長さ（以上）の部分列で要素の最大公約数がとなるようなものはないため，答えはです．

5 10
120 50 40 90 30

5

です．

5 10
120 80 40 60 520

-1

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