みんなでジョギング

赤ベコ小学校では、生徒全員が参加する、ちょっと変わったジョギングをします。生徒は、それぞれ独自の周回コースを、自分のペースで走ります。それぞれ自分のコースを 1 周すると小学校に戻ってきます。全員が小学校を同時にスタートしてから、全員が同時に小学校で最初に出会うのは、それぞれ何周したときでしょうか?

生徒の人数 n、各生徒のコースの 1 周の距離 d (km) 、各生徒の走る速さ v (km/時間)を入力とし、全員が小学校を同時にスタートしてから次に同時に小学校に位置するのは、各生徒がそれぞれ何周したときかを出力するプログラムを作成してください。なお、各生徒は 2³¹-1 周を超えて走ることはありません。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロひとつの行で示されます。 各データセットは以下の形式で与えられます。

n
d1 v1
d2 v2
:
dn vn

1 行目に生徒の人数 n (2 ≤ n ≤ 10) が与えられます。続く n 行に i 人目の生徒のコースの１周の距離 d_i (1 ≤ d_i ≤ 10000) と走る速さ v_i (1 ≤ v_i ≤ 10000) が与えられます。

データセットの数は 2000 を超えません。

Output

入力データセットごとに、各生徒の周回数を出力します。各生徒の周回数は入力の順番に従ってそれぞれ１行に出力してください。

Sample Input

2
4 3
5 4
5
789 289
166 46
9 4
617 252
972 303
2
8 5
32 20
0

Output for the Sample Input

15
16
1598397732
1209243492
1939462992
1782294192
1360317793
1
1

---