As you may know, there are currently two main sets of measurement units in the world:
the metric system and the imperial system. The imperial system receives its name from
the British empire, which was the place of its invention and its main user until recently.
Nowadays, Britain’s heir, the United States of America, is the only country where a
variation of the imperial system is the official measurement system.
For a particular magnitude, in a given measurement system there are N different units
U1 , U2 , . . . UN (the number of units depends on both the magnitude and the system). For
every i (1 ≤ i ≤ N − 1), a certain number of Ui is equivalent to a certain number of
Ui+1 . In the metric system we always have that 1Ui is equivalent to 10Ui+1 . For instance,
1 decimeter is equivalent to 10 centimeters, 1 gram is equivalent to 10 decigrams, and
1 decaliter is equivalent to 10 liters. On the contrary, in some variations of the imperial
system we may have other positive integers instead of 1 and 10. For instance, 32 drams
are equivalent to 875 grains.
Since you were born and raised using the much more sensible metric system, you need help
learning the imperial system and its variations. You want to be able to transform directly
from U1 to UN , that is, you need to know that a certain number of U1 is equivalent to a
certain number of UN . To ease further calculations, you want to express the equivalence
using only integers values, and these values must be as small as possible.

Input

Each test case is described using several lines. The first line contains an integer N
indicating the number of units in the measurement system (2 ≤ N ≤ 10). Line i of the
next N − 1 lines describes the relationship between units Ui and Ui+1 with two integers
Ai and Bi representing that Ai Ui is equivalent to Bi Ui+1 (1 ≤ Ai < Bi ≤ 100). The end
of input is indicated with a line containing a single −1.

Output

For each test case, output a single line with two positive integers C and D representing
that CU1 is equivalent to DUN . If there are several alternatives, choose the minimum
possible value for C.

Example

Input: 
5
1 2
2 3
3 4
2 5
2
6 9
-1

Output: 
1 10
2 3