SIMPLE - Make It Simple

no tags 

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

hide comments
ariesdwi4: 2016-11-11 16:31:14

may i input in two line ?

Francky: 2013-05-13 13:53:26

It is a tutorial problem.
@psetter : please put in classical only sufficient task ; this one is way too easy.


Added by:hossamyosef
Date:2013-05-13
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:FCIS/ASU Local Contest 2013