В настоящее время миру известно огромное количество сенсационных археологических находок. Во время последних раскопок были обнаружены носители информации, относящиеся к эпохе программирования XX века. Расшифровка файлов позволила ученым доказать гипотезу о том, что древние программисты обладали искусством производить простейшие арифметические операции с дробями. Многие тексты были расшифрованы, многие загадки были разгаданы. Однако среди нерешенных оказалась задача о вычислении наименьшей положительной дроби, при делении которой на каждую из n заданных дробей получаются целые числа.
Возможно, это удастся сделать вам...
В первой строке записано одно целое число n — количество заданных дробей (1 ≤ n ≤ 6). В каждой из следующих n строк записано два целых числа ai, bi — числитель и знаменатель несократимой дроби (1 ≤ ai ≤ 103, 1 ≤ bi ≤ 109).
В единственной строке запишите через пробел два положительных целых числа — числитель и знаменатель наименьшей несократимой дроби, удовлетворяющей условию задачи.
2
1 2
3 4
3 2
2
2 3
4 5
4 1
