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.
Therefore,
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 resilience
Input Format
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 .
Constraints
Output Format
For each print the answer on a separate line.
Sample Input 0
1
4 10
Sample Output 0
12
Explanation 0
See problem description