시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 694 98 87 22.656%

문제

프로불편러 지수는 딱 떨어지지 않는 수는 질색이다. 거스름돈이 남는 것도 딱 질색이다. 지수가 아이템을 사려 하는데, 아이템의 가격은 다 분수로 이루어져 있다. 지금은 가령, 3/2코인을 사려고 2코인을 적립하고 결제하면 1/2코인이 남아버리는 것이다. 그래서 개발사에게 모든 아이템을 딱 떨어지게 나눌 수 있는 가격 단위를 건의하기 위해, 새로운 가격 단위는 최대 몇 코인인지를 구하려고 한다.

N개의 종류의 아이템을 딱 떨어지게 나눌 수 있는 코인 단위를 구하라. 이때 아이템과 코인은 모두 분수 형태로 나와야 한다.

입력

첫 번째 줄에는 아이템의 개수 N (1 ≤ N ≤ 50)이 주어진다.

두 번째 줄부터는 한 줄에 분자 A, 분모 B (1 ≤ A, B ≤ 40) 쌍이 주어진다. 이는 기약분수 형태가 아닐 수도 있다.

출력

새로운 코인 단위의 분자, 분모를 공백으로 구분하여 출력한다. 단, 기약분수 형태이다.

예제 입력 1

2
1 4
2 5

예제 출력 1

1 20

예제 입력 2

3
1 3
5 2
3 4

예제 출력 2

1 12