Anything Goes to One

問題文

要素数 $N$ の数列 $a=(a_1,\ a_2,\cdots ,a_N)$ が与えられます。ここで、$a$ の要素は全て互いに相異なります。

$m=1,\ 2,\ \cdots ,K$ の全てに対して、以下の問題を解いてください。

【問題】
整数 $x$ があり、はじめ $x=m$ である。これに対して、以下の操作 (1) と (2) を任意の順番で任意の回数行うことができる。

• (1) : $x$ を $x+1$ に置き換える。
• (2) : $x$ が $a_i$ で割り切れるような整数 $i\ (1\le i\le N)$ を選び、$x$ を $\dfrac{x}{a_i}$ で置き換える。

あなたは、操作によって $x=1$ である状態にしたい。必要な操作回数の最小値は何回か？

なお、この制約下では、どのような $m\ge 1$ に対しても $x=1$ にするような操作列が存在することが証明できます。

入力

制約

• $1\le N\le 10^5$
• $2\le K\le 2\times 10^5$
• $2\le a_i\le 2\times 10^5$
• $i\neq j$ ならば $a_i\neq a_j$
• 入力は全て整数

出力

$K$ 行出力し、$i\ (1\le i\le K)$ 行目には、$m=i$ の場合の答えを出力してください。
出力が多いので、高速な入出力を用いることを推奨します。

入力例1

2 5  
3 5  

出力例1

0
2
1
2
1

例えば、$m=2$ のとき、以下のようにして２回で $x=1$ とすることが可能です。

• 操作１を行い、$x=3$ とする。
• 操作２で $i=1$ を選び、$x=\dfrac{3}{3}=1$ とする。

$m=5$ のときは、以下のようにして１回で $x=1$ とすることが可能です。

• 操作２で $i=2$ を選び、$x=\dfrac{5}{5}=1$ とする。

入力例2

2 8
2 7  

出力例2

0
1
3
2
3
2
1
3