4/8 can be simplified to 2/4 and 2/4 can be simplified to 1/2. In this problem you will be given a rational number X/Y and your task is to make it in its simplest form. For example 1/2 is the simplest form of 4/8.

Input

The first line of input will be the number of test cases. Each case have one line on the form X/Y where X is the numerator and Y is the denominator, 1 <= X <= Y <= 1,000,000.

Output

For each test case print “Case C: A/B” without quotes where C is the case number starting with 1 and A/B is the simplest form of X/Y.

Example

Input:
3
4/8
2/5
7/21

Output:
Case 1: 1/2
Case 2: 2/5
Case 3: 1/3