import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.Map;

class Ideone {
	
	static final int maxn = 40000;
	static int len[] = new int[maxn], link[] = new int[maxn], count[][] = new int[2][maxn];
	static boolean vis[] = new boolean[maxn];
	static HashMap<Character, Integer> to[] = new HashMap[maxn];
	static int size = 0, last, res;
	
	public static void init() {
		for (int i = 0; i < size; i++) {
			to[i].clear();
			len[i] = link[i] = count[0][i] = count[1][i] = 0;
			vis[i] = false; 
		}
		link[0] = -1;
		size = 1;
		last = res = 0;
	}
	
	public static void addCharacter(Character c) {
		int p = last;
		last = size++;
		len[last] = len[p] + 1;
		for (; p != -1 && !to[p].containsKey(c); p = link[p])
			to[p].put(c, last);
		if (p == -1)
			return;
		int q = to[p].get(c);
		if (len[q] == len[p] + 1) {
			link[last] = q;
			return;
		}
		int cl = size++;
		to[cl].putAll(to[q]);
		link[cl] = link[q];
		len[cl] = len[p] + 1;
		link[last] = link[q] = cl;
		for (; p != -1 && to[p].containsKey(c) && to[p].get(c) == q; p = link[p])
			to[p].put(c, cl);
	}
	
	public static int dfs(int x, int k) {
		if (vis[x])
			return res;
		vis[x] = true;
		count[0][x] = count[1][x] = 0;
		for (Map.Entry<Character, Integer> it : to[x].entrySet())
			if (it.getKey() == '#')
				count[0][x]++;
			else
				if (it.getKey() == '$')
					count[1][x]++;
				else {
					dfs(it.getValue(), k);
					count[0][x] += count[0][it.getValue()];
					count[1][x] += count[1][it.getValue()];
				}
		if (x != 0) {
			int x1 = count[0][x] != 0 ? 1 : 0;
			int x2 = count[1][x] == k ? 1 : 0;
			res += (x1 * x2 * (len[x] - len[link[x]]));
		}
		return res;
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		for (int i = 0; i < maxn; i++)
			to[i] = new HashMap<Character, Integer>();
		
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		
		int t = Integer.parseInt(bf.readLine());
		
		for (int tc = 1; tc <= t; tc++) {
			out.println("Case #" + tc + ":");
			String s1 = bf.readLine();
			String s2 = bf.readLine();
			int k = Integer.parseInt(bf.readLine());
			int n = s1.length(); int m = s2.length();
			init();
			for (int i = 0; i < n; i++)
				addCharacter(s1.charAt(i));
			addCharacter('#');
			for (int i = 0; i < m; i++)
				addCharacter(s2.charAt(i));
			addCharacter('$');
			
			out.println(dfs(0, k));
		}
		out.flush();
		//out.close();
		
	}
}