I Hate Change

Interview

Time limit1sMemory limit512 MB

Summary

Given N fractions, find the largest fraction that divides every given fraction exactly, with the answer reduced to lowest terms.

Level: Medium6 of 10
Topics: Math, Number theory, Implementation, Brute force
Solved: No attempts yet

Problem

Jisoo, a complainer, hates numbers that do not divide evenly. She also hates leftover change. Jisoo wants to buy items, and the prices of the items are all fractions. For example, to buy an item costing 3/2 coins, she saves 2 coins and pays, leaving 1/2 coin behind. So, to propose to the developer a price unit that divides all items evenly, she wants to find the largest possible new price unit in coins.

Find a coin unit that divides N kinds of items evenly. Both the items and the coin must be expressed as fractions.

Input

The first line gives the number of items N (1 ≤ N ≤ 50).

From the second line onward, each line gives a pair of numerator A and denominator B (1 ≤ A, B ≤ 40). The fraction may not be in lowest terms.

Output

Print the numerator and denominator of the new coin unit separated by a space. The fraction must be in lowest terms.

Examples2

Example 1
Input
```
2
1 4
2 5
```
Expected output
```
1 20
```
Example 2
Input
```
3
1 3
5 2
3 4
```
Expected output
```
1 12
```