Real Phobia#3047
Sign in

Real Phobia

1 second
64 megabytes
Very easy

Bert is a programmer who has a real fear of floating point arithmetic. He prefers to use rational numbers in his programs, but does not like it when the denominator becomes too large. Your task is to help Bert by writing a program that decreases the denominator of a rational number, introducing the smallest possible error.

For a rational number , where B > 2 and 0 < A < B, your program should find a rational number such that:

  1. 0 < C < D < B, and

  2. the error |A/B - C/D| is minimized over all possible values of and , and

  3. is the smallest such positive integer.

Input

The input starts with an integer (1 \leq K \leq 1000) that represents the number of cases. Each of the following lines describes a case as a fraction in the form of two integers, and , separated by "/", such that:

  1. is a -bit integer strictly greater than , and

  2. 0 < A < B.

Output

For each case, output a single line containing a fraction in the form of two integers separated by "/".

Examples

Example 1

Loading
Loading