Fractions again

Time Limit: 1 Second    Memory Limit: 32768 KB

Once upon a time, in a small Kingdom of Multiland the wise and good King Shuvarr the Reformer decided to repair the economy of his poor country. In order to save up some lead, which is very important to Multiland's industry he commanded to reduce usage of pencils. Because citizens of Multiland are very accurate they used very precised fractions. So the wise king limited in his decree the maximum value of denominators. Help Multilanders in this strange situation !

TASK

Your program should

  • read the fraction and the limit

  • write the fraction which is nearest to the given one and it's denominator is less or equal to the limit

  • if there are more solutions Your program should give the number with the lowest denominator

Input

In the first line of input there is C (1<=C<=100000) which is the number of the test cases. The next 2*C lines contain :

  • the fraction N/D (1<= N <= D <= 10^9), numerator (N) and denominator (D) are seperated by '/'

  • the number L (1<=L<=10^6) which is the limit of the denominator

Output

Your program has to write C lines, each of them consisting of the numerator, slash and denominator of the simplified fraction.

Sample Input

3
100/200
10
3/10
5
9/11
8

Sample Output

1/2
1/3
5/6
Submit

Source: 3MG_Contest