1373 - Fraction to be Integer

時間制限 2 秒 / メモリ制限 512 MB / 得点 100 / Writer もけ / x 8 / 統計 /

TLE
2sec
MLE
512MB
得点
100

問題

$N$ 個の分数 $F_i = \dfrac{n_i}{d_i}$ $(1 \leq i \leq N)$ が与えられます。
$F_i$ との積がすべて整数となるような最小の正の分数を求めてください。

入力

入力は以下の形式で標準入力から与えられる。 

$N$
$n_1$ $d_1$
$n_2$ $d_2$
$\vdots$
$n_N$ $d_N$

出力

答えとなる分数を以下の形式で出力せよ。

答えとなる分数の分子を $x$、分母を $y$ とする。

  • 既約分数化すること。すなわち $x$ と $y$ が互いに素となるようにすること。
  • $x, y$ を空白区切りで出力すること。
  • 出力の末尾には改行を入れること。

制約

  • $1 \leq N \leq 10$
  • $1 \leq n_i, d_i \leq 1,000,000$
  • 入力はすべて整数である。
  • 答えとなる分数の分子と分母が 64 bit 整数型におさまらなくなるような入力は与えられない。

入出力例

入力例１

3
8 7
24 4
16 14

出力例１

7 2

$\dfrac{7}{2}$ と各 $F_i$ の積はそれぞれ、
$\dfrac{8}{7} \times \dfrac{7}{2} = 4, \dfrac{24}{4} \times \dfrac{7}{2} = 21, \dfrac{16}{14} \times \dfrac{7}{2} = 4$
となり、すべて整数となります。
このほかに、$\dfrac{35}{4}$ や $\dfrac{63}{8}$ も $F_i$ との積がすべて整数となりますが、$\dfrac{7}{2}$ が最小です。

入力例２

4
30 2
90 3
60 4
60 5

出力例２

1 3

入力例３

7
10922 245
426464 131
413570 5401
435864 677
996046 6761
55186 315
85810 3273

出力例３

7790734816554582585 2