- All Contests
- ProjectEuler+
- Project Euler #243: Resilience

# Project Euler #243: Resilience

# Project Euler #243: Resilience

_{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