Rational Irrationals

Time limit2sMemory limit512 MB

Summary

For each prime p and bound n, output the two fractions with numerator and denominator at most n that bracket sqrt(p) most tightly, in lowest terms.

Level: Medium5 of 10
Topics: Math, Number theory, Sorting, Brute force
Solved: No attempts yet

Problem

A rational number is a number that can be written as a ratio of two integers. For a prime number $p$ , one of the elementary theorems in number theory is that no rational number equals $\sqrt{p}$ . Such numbers are called irrational numbers. It is also known that rational numbers come arbitrarily close to $\sqrt{p}$ .

Given a positive integer $n$ , define the set $Q_n$ of all rational numbers that can be written as a ratio of two positive integers, both less than or equal to $n$ . For example, $Q_4$ is the set of 11 rational numbers {1/1, 1/2, 1/3, 1/4, 2/1, 2/3, 3/1, 3/2, 3/4, 4/1, 4/3}. 2/2, 2/4, 3/3, 4/2, and 4/4 are not included because they equal 1/1, 1/2, 1/1, 2/1, and 1/1, respectively.

Your job is to write a program that reads two integers $p$ and $n$ and outputs two rational numbers $x/y$ and $u/v$ such that $u/v < \sqrt{p} < x/y$ and no other element of $Q_n$ lies between $u/v$ and $x/y$ . When $n$ is greater than $\sqrt{p}$ , such a pair of rational numbers always exists.

Input

The input consists of lines, each containing a prime number $p$ and an integer $n$ , two positive integers in the following format.

p n

The two numbers are separated by a space. You can assume that $p$ and $n$ are less than 10000 and that $n$ is greater than $\sqrt{p}$ . The end of the input is indicated by a line consisting of two zeros.

Output

For each input line, output one line containing the two rational numbers $x/y$ and $u/v$ ( $x/y > u/v$ ) separated by a space in the following format.

x/y u/v

They must be irreducible. For example, 6/14 and 15/3 are not accepted. They must be reduced to 3/7 and 5/1, respectively.

Examples1

Example 1

Input

Expected output

3/2 4/3
7/4 5/3
85/38 38/17