#include <bits/stdc++.h>

using namespace std;

const int maxn = 4e4;
int len[maxn], link[maxn], cnt[maxn][2], used[maxn];
map<char, int> to[maxn];
int sz, last, ans;

void init(int n)
{
    for(int i = 0; i < sz; i++)
    {
        to[i].clear();
        len[i] = link[i] = cnt[i][0] = cnt[i][2] = used[i] = 0;
    }
    link[0] = -1;
    sz = 1, last = ans = 0;
}

void add_letter(char c)
{
    int p = last;
    last = sz++;
    len[last] = len[p] + 1;
    for(; p != -1 && !to[p][c]; p = link[p]) to[p][c] = last;
    if(p == -1) return;
    int q = to[p][c];
    if(len[q] == len[p] + 1)
    {
        link[last] = q;
        return;
    }
    int cl = sz++;
    to[cl] = to[q];
    link[cl] = link[q];
    len[cl] = len[p] + 1;
    link[last] = link[q] = cl;
    for(; p != -1 && to[p][c] == q; p = link[p]) to[p][c] = cl;
}

int dfs(int x, int k)
{
    if(used[x]) return ans;
    used[x] = 1;
    cnt[x][0] = cnt[x][1] = 0;
    for(auto it: to[x])
    {
        if(it.first == '#')
            cnt[x][0]++;
        else if(it.first == '$')
            cnt[x][1]++;
        else
        {
            dfs(it.second, k);
            cnt[x][0] += cnt[it.second][0];
            cnt[x][1] += cnt[it.second][1];
        }
    }
    if(x)
        ans += (cnt[x][0] != 0) * (cnt[x][1] == k) * (len[x] - len[link[x]]);
    return ans;
}

 main()
 {
     ios::sync_with_stdio(0);
     cin.tie(0);
     int t;
     cin >> t;
     for(int i = 1; i <= t; i++)
     {
         string a, b;
         cin >> a >> b;
         init(a.size() + b.size() + 2);
         for(auto c: a) add_letter(c);
         add_letter('#');
         for(auto c: b) add_letter(c);
         add_letter('$');
         int k;
         cin >> k;
         cout << "Case #" << i << ":\n" << dfs(0, k) << "\n";
     }
 }