using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
String[] ans;
int noOfTC = Int32.Parse(Console.ReadLine());
String[] s1= new String[noOfTC];
String[] s2 = new String[noOfTC];
int[] L = new int[noOfTC];
for (int i = 0; i < noOfTC; i++)
{
s1[i] = Console.ReadLine();
s2[i] = Console.ReadLine();
L[i] = Int32.Parse(Console.ReadLine());
}
ans = new String[noOfTC];
for (int i = 0; i < noOfTC; i++)
ans[i] = start(s1[i], s2[i], L[i]);
for (int i = 0; i < noOfTC; i++)
Console.WriteLine(ans[i]);
}
private static String start(String s1, String s2, int L)
{
if (s1.Length > s2.Length)
{
String t = s1;
s1 = s2; s2 = t;
}
String testStr, temp = "";
int count = 0, subCount = 0;
int k = 0;
while (k < L)
{
k++;
for (int i = 0; i <= s1.Length-k; i++)
{
testStr = ""; subCount = 0;
testStr = s1.Substring(i, k );
subCount = isSubStrFound(s2, testStr);
count += subCount;
}
temp += count + " ";
count = 0;
}
return temp;
}
public static int isSubStrFound(string text, string pattern)
{
if (!text.Contains(pattern))
return 0;
else
return 1;
}
}
}