402912: GYM100942 M The smallest fraction

Currently the world knows a great number of sensational archaeological discoveries. Data storage devices relating to the period of programming of the XX century were discovered during recent excavations. Decryption of files allowed scientists to prove the hypothesis that ancient programmers were able to make simple arithmetic operations with fractions. Many texts have been deciphered, many mysteries have been solved. However one problem has remained unsolved: a calculation of the smallest positive fraction that, if divided by each of n given fractions, results in an integer number.

May be you will manage to solve it...

The first line contains an integer n (1 ≤ n ≤ 6). Each of the following n lines contain two integers a_i, b_i that are numerator and denominator of irreducible fraction (1 ≤ a_i ≤ 10³,  1 ≤ b_i ≤ 10⁹).

Print two positive integers separated by space that are numerator and denominator of the smallest irreducible fraction satisfying the condition of the problem.

2
1 2
3 4

3 2

2
2 3
4 5

4 1