J - Two Mirrors

マルチテストについての説明はこちら (サンプル問題を確認されていない方のみお読みください。)

配点： 点

平面上に鏡が 枚あります．
具体的には，直線 および 直線 が鏡です．(ただし は互いに素である 正整数)

点 から 軸負の向きに光線を発射します．
鏡に当たった光線は，入射角と反射角が等しくなるように反射します．

• 反射前の光線の延長線と鏡との交点を通る，鏡に垂直な直線を とする．
• 入射角/反射角 とは，それぞれ と 反射前/反射後 の光線とがなす角度をいう．

光線は 枚の鏡の間で交互に有限回の反射を行います．

反射は何回起こりますか？ 求めてください．

• は互いに素である 整数

各テストケースの入力は，それぞれ以下の形式で与えられる：

答えを出力せよ．

1
1 1

3

点 でこの順に反射します．

1
2 1

2

5
1 1
1 10
1 100
1 1000
1 10000

3
31
314
3141
31415