Farey sequences#1512

Farey sequences

1 second
128 megabytes
Easy

A fraction is called a proper fraction if it lies between and , and and have no common divisors other than . For any natural number n \geq 1, the Farey sequence of order , denoted as , is the sequence of all proper fractions with denominators not exceeding , together with the "fraction" , arranged in increasing order. For example, the sequence is:

prb1512.gif

Given , find the -th fraction in the sequence .

Input

Each line contains two natural numbers and , with 1 \leq n \leq 1000, and is sufficiently small that the -th term exists in . (The length of is approximately 0.3039635 n^2).

Output

For each input pair, print the -th element of in the format shown in the example.

Examples

Example 1

Loading
Loading