問題文


個の歯車があり、 番目の歯車の歯数は です。
を満たす について、 番目の歯車と 番目の歯車が嚙み合っています。
歯車が空回りすることはなく、歯 つを噛み合わせながら回ります。

個のクエリが与えられます。 番目のクエリでは、以下の問いの答えてください。

  • 番目の歯車を回以上 回転させるために、 番目の歯車を最低で何回転させれば良いか、"整数"で答えてください。

制約


入力はすべて整数である。

入力







出力


番目のクエリの答えを行目に整数で出力せよ。

サンプル


入力1
5 4
2 4 8 12 7
1 3
3 4
4 5
2 5
出力1
4
2
1
2

つ目のクエリについて、 番目の歯車は以下のようになっています。
図
つ目の歯車を回転させることで、 つ目の歯車がちょうど 回転します。
つ目の歯車が回転することで、 つ目の歯車がちょうど 回転します。
よって、 つ目の歯車を 回転させるためには、 回転が最小です。

つ目のクエリについて、
つ目の歯車を 回転させるだけでは、 つ目の歯車は 回転に満たないです。
つ目の歯車を 回以上、回転させるために必要な最小回転数(整数)として、 回転が答えになります。

提出


Go (1.14)