We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

Loading...

- All Contests
- ProjectEuler+
- Project Euler #71: Ordered fractions

# Project Euler #71: Ordered fractions

# Project Euler #71: Ordered fractions

Consider the fraction, , where and are positive integers. If and , it is called a reduced proper fraction.

If we list the set of reduced proper fractions for , (where is the denominator) in ascending order of size, we get:

It can be seen that is the fraction immediately to the left of .

By listing the set of reduced proper fractions for in ascending order of size, find the numerator and denominator of the fraction immediately to the left of .

**Input Format**

First line of input contains an integer , number of test cases.

Next lines contain separated by space.

**Constraints**

**Output Format**

Print the numerator and denominator separated by a space corresponding to each test case on a new line.

**Sample Input**

```
5
3 7 8
3 5 8
4 5 8
6 7 8
1 5 8
```

**Sample Output**

```
2 5
4 7
3 4
5 6
1 6
```