Anything Goes to One

2 secs 1024 MB
eSeF

問題文


要素数 の数列 が与えられます。ここで、 の要素は全て互いに相異なります。

の全てに対して、以下の問題を解いてください。


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

  • (1) : に置き換える。
  • (2) : で割り切れるような整数 を選び、 で置き換える。

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


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

入力



制約


  • ならば
  • 入力は全て整数

出力


行出力し、 行目には、 の場合の答えを出力してください。
出力が多いので、高速な入出力を用いることを推奨します。

入力例1


2 5  
3 5  

出力例1


0
2
1
2
1

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

  • 操作1を行い、 とする。
  • 操作2で を選び、 とする。

のときは、以下のようにして1回で とすることが可能です。

  • 操作2で を選び、 とする。

入力例2


2 8
2 7  

出力例2


0
1
3
2
3
2
1
3

提出


Go (1.14)