AOJ 3519 - Find a Fraction

Find a Fraction

Time Limit: 1000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 3637
64-bit integer IO format: %I64d Java class name: Main

Submit Status Statistics

Font Size:

Description

Given two non-negative rational numbers A and B(A<B), your task is to find a fraction between (A,B).
Maybe there're many fractions in this interval. In this condition, output the fraction with the smallest sum of its denominator and molecular.

Input

The first line is an integer T(<=25) indicating the case number.
The next T lines each contains two strings, namely A and B.
A rational number contains characters '0'~'9','.','[',']' only.
Digits between '[' and ']' are recurring decimal's cycle parts.(0.[6] = 0.666...,etc.)
You may assume the input are all logical, and all the strings are no more than 16.

Output

For each case, output a fraction(as the format below) with the smallest sum of its denominator and molecular.

Sample Input

4
0 0.5
0.[6] 0.[7]
11.0[8] 11.1[5]
1.[142857] 3.[142857]

Sample Output

Case 1: 1/3
Case 2: 3/4
Case 3: 78/7
Case 4: 2/1

Source

2010 ACM-ICPC Multi-University Training Contest（19）——Host by HDU