#include <bits/stdc++.h>
    using namespace std;
    inline int32_t max(int32_t a, int32_t b)
	{ 
	    return a - ((a-b) & (a-b)>>31);
	}
    string s1;
    int z[16005], mn[8005], mx, cnt[8005], n2, m, ret, k1;
    void getZ(int k) {
	    mx = 0;	
	 	int n = n2 + m + 1;
	   	
	    for (int i = k+1, l = 0, r = 0; i < n; ++i) {
	        if (i <= r)
	            z[i] = min (r - i + 1, z[i - l + k]);
	        while (i + z[i] < n && s1[z[i]+k] == s1[i + z[i]])
	            ++z[i];
	        if (i + z[i] - 1 > r)
	            l = i, r = i + z[i] - 1;
	        if(i > n2) {
		    	mx = max(z[i], mx);
	    		cnt[z[i]]++;
		    }
		    if(i<n2) 	mn[i] = max(mn[i], z[i]);
		    
	    }
	    
	    for (int j = mx ; j > 1 ; j--)
	    	cnt[j - 1] += cnt[j];
	     
	    //calculating number of k occurrences
	    for (int j = mn[k] + 1; j <= mx; j++)
		    if (cnt[j] == k1) ret++;
    
    	/*cout<<s1.substr(k,n)<<" "<<k<<endl;
    	for(int p = k; p < n; ++p)
			cout<<z[p]<<" ";
		cout<<endl;*/
    }
     
    int main()
    {
     
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t , c=1 , k;
    cin >> t;
    for (; t; t--)
    {
	    cout <<"Case #" << c++ << ":" << "\n";
	    string s12, s2;
	    cin >> s12;
	    cin >> s2;
	    cin >> k1;
	    n2 = s12.length(); 
	    m = s2.length();
	    s1 = "";
	    s1 += s12;
	    s1 += "$";
	    s1 += s2;
	  	ret = 0;
	    memset (mn , 0 , sizeof mn);

	    for (int i = 0 ; i < n2; i++)
	    {
		    memset (z , 0 , sizeof z);
		    memset (cnt , 0 , sizeof cnt);
		    getZ(i);
	    }
	     
		cout<<ret<<"\n";
	 }
    return 0;
    }