public static void main(String[] args) {
		long start = System.currentTimeMillis();
		try {
			FileReader fr = new FileReader(SourcePath.getInputPath() + "/googleCodeJam/round1C2014/A-small-attempt0.in");
			FileWriter fw = new FileWriter(SourcePath.getOutputPath() + "/googleCodeJam/round1C2014/A-small-attempt0.out");

			BufferedReader br = new BufferedReader(fr);
			BufferedWriter bw = new BufferedWriter(fw);
			
			int numOfCases = Integer.valueOf(br.readLine());
			String[] caseKeys;
			
			StringBuffer outPut = new StringBuffer();
			long element;
			long denominator;
			String result;
			
			for (int i = 0; i < numOfCases; i++){
				caseKeys = br.readLine().split("/");
				
				element = Long.valueOf(caseKeys[0]);
				denominator = Long.valueOf(caseKeys[1]);
				
				result = getMinNumber(element, denominator);
				
				System.out.println("Case #" + (i + 1) + ": " + result);
				outPut.append("Case #").append(i+1).append(": ").append(result).append("\n");
			}
			
			br.close();
			fr.close();
			bw.write(outPut.toString());
			bw.flush();
			bw.close();
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		} catch (NumberFormatException e) {
			e.printStackTrace();
		} catch (IOException e) {
			e.printStackTrace();
		}
		long end = System.currentTimeMillis();
		
		System.out.println(end - start);
	}