// Arup Guha
// 1/27/2013
// Solution to 2011 Rocky Mountain Regional Problem: User Names.
import java.util.*;

public class g {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);

		String line = stdin.nextLine();

		int caseNum = 1;

		// Go through each case.
		while (true) {

			StringTokenizer tok = new StringTokenizer(line);
			int n = Integer.parseInt(tok.nextToken());
			int max = Integer.parseInt(tok.nextToken());

			// Got to last case.
			if (n == 0) break;

			// Read in strings.
			String[] original = new String[n];
			for (int i=0; i<n; i++) {
				original[i] = stdin.nextLine();
			}

			// Solve.
			System.out.println("Case "+caseNum);
			solve(original, max);
			line = stdin.nextLine();
			caseNum++;
		}
	}

	public static void solve(String[] original, int max) {

		// Will store usernames in here.
		HashMap<String,String> list = new HashMap<String,String>();

		for (int i=0; i<original.length; i++) {

			StringTokenizer tok = new StringTokenizer(original[i]);

			// Get first and last names.
			String first = tok.nextToken();
			String last = tok.nextToken();
			while (tok.hasMoreTokens())
				last = tok.nextToken();

			// Make lowercase and remove non-letters.
			first = fix(first);
			last = fix(last);

			// First try.
			String user = first.charAt(0) + last.substring(0, Math.min(max-1, last.length()));
			if (!list.containsKey(user)) {
				System.out.println(user);
				list.put(user,user);
				continue;
			}

			// Try one digit.
			user = first.charAt(0) + last.substring(0, Math.min(max-2, last.length()));
			boolean found = false;
			for (int j=1; j<=9; j++) {
				String tmpUser = user + j;
				if (!list.containsKey(tmpUser)) {
					System.out.println(tmpUser);
					list.put(tmpUser, tmpUser);
					found = true;
					break;

				}
			}

			// One digit worked...
			if (found) continue;

			// Try two digits - Guaranteed to work...
			user = first.charAt(0) + last.substring(0, Math.min(max-3, last.length()));
			for (int j=10; j<=99; j++) {
				String tmpUser = user + j;
				if (!list.containsKey(tmpUser)) {
					System.out.println(tmpUser);
					list.put(tmpUser, tmpUser);
					break;
				}
			}

		}

	}

	public static String fix(String s) {

		// Make lowercase.
		s = s.toLowerCase();
		String ans = "";

		// Only add letters.
		for (int i=0; i<s.length(); i++)
			if (s.charAt(i) >= 'a' && s.charAt(i) <= 'z')
				ans = ans+ s.charAt(i);
		return ans;
	}
}