// Arup Guha
// 7/20/2015
// Solution to 2010 UCF Fall Locals Problem: LCA

import java.util.*;
import java.io.*;

public class lca {

	public static void main(String[] args) throws Exception {

		BufferedReader stdin = new BufferedReader(new InputStreamReader(System.in));
		int numCases = Integer.parseInt(stdin.readLine().trim());
		StringBuilder sb = new StringBuilder();

		// Process all cases, use the string builder for speed up.
		for (int loop=1; loop<=numCases; loop++) {
			StringTokenizer tok = new StringTokenizer(stdin.readLine());
			boolean[] one = getBinArray(tok.nextToken());
			boolean[] two = getBinArray(tok.nextToken());
			sb.append("Case #"+loop+": "+solve(one,two)+"\n\n");
		}
		System.out.print(sb);
	}

	public static boolean[] getBinArray(String s) {
		int extra = bits(s.charAt(0));
		int len = (s.length()-1)*4 + extra;
		boolean[] b = new boolean[len];

		// Annoying - do first possibly unequal set.
		for (int i=extra-1, j=0; i>=0; i--,j++)
			if (on(s.charAt(0), i))
				b[j] = true;

		// Do the rest...
		for (int i=extra; i<len; i+=4)
			for (int j=0; j<4; j++)
				if (on(s.charAt( (i-extra)/4 + 1 ), 3-j))
					b[i+j] = true;
		return b;
	}

	// Returns true if hex character c is on a bit bit.
	public static boolean on(char c, int bit) {
		if (c >= 'A') {
			int val = c - 'a' + 10;
			return (val & (1 << bit)) > 0;
		}
		return ((c - '0') & (1 << bit)) > 0;
	}

	// Returns # of binary bits in hex char c.
	public static int bits(char c) {
		if (c < '2') return 1;
		if (c < '4') return 2;
		if (c < '8') return 3;
		return 4;
	}

	// Returns the result by counting the number of matching starting bits.
	public static String solve(boolean[] one, boolean[] two) {
		int i = 0;
		while (i < one.length && i < two.length && one[i] == two[i]) i++;
		return convert(one, i);
	}

	public static String convert(boolean[] b, int len) {

		// Get first char length.
		int extra = len%4;
		if (extra == 0) extra = 4;

		// Fill in first char.
		char[] buffer = new char[(len+3)/4];
		buffer[0] = convertBits(b, 0, extra);

		// Fill in rest.
		for (int i=extra; i<len; i+=4)
			buffer[(i-extra)/4+1] = convertBits(b, i, i+4);
		return new String(buffer);
	}

	// Converts b[start..end] into one hex char.
	public static char convertBits(boolean[] b, int start, int end) {

		// Build equivalent value of bits.
		int val = 0;
		for (int i=start; i<end; i++) {
			if (b[i])
				val = (val << 1) + 1;
			else
				val = (val << 1);
		}

		// Convert decimal to hex char.
		return val <= 9 ? (char)(val + '0') : (char)(val + 'a' - 10);
	}
}