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

配点：$300$ 点

問題文

$x\text{‐}y$ 平面上に鏡が $2$ 枚あります．
具体的には，直線 $Px - Qy = 0$ および 直線 $y = 0$ が鏡です．(ただし $P, Q$ は互いに素である $2$ 正整数)

点 $(10^{100}, 1)$ から $x$ 軸負の向きに光線を発射します．
鏡に当たった光線は，入射角と反射角が等しくなるように反射します．

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

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

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

制約

• $1 \leq \Phi \leq 100$
• $1 \leq P, Q < 2^{16}$
• $P, Q$ は互いに素である $2$ 整数

入力

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

出力

答えを出力せよ．

サンプル

1
1 1

3

点 $(1, 1), (1, 0), (1, 1)$ でこの順に反射します．

1
2 1

2

5
1 1
1 10
1 100
1 1000
1 10000

3
31
314
3141
31415