This problem is a programming version of Problem 243 from projecteuler.net
A positive fraction whose numerator is less than its denominator is called a proper fraction.
For any denominator , there will be proper fractions.
We shall call a fraction that cannot be cancelled down a resilient fraction.
Furthermore we shall define the resilience of a denominator to be the ratio of its proper fractions that are resilient.
For example, for : are the resilient fractions.
In fact, is the smallest denominator having a resilience
Given pairs of integers , representing numerator and denominator of a proper fraction , find the smallest denominator , having
The first line of each test file contains a single integer . Next lines each contain a pair of integers , , separated by a single space, representing .
For each print the answer on a separate line.
Sample Input 0
Sample Output 0
See problem description