#include 
#include 
#include 
#include 
using namespace  std;
string a,b;
int memo[105][105][105];
int k;
int f(int i, int j,int k_){
    if (k_==k){
        return 0;
    }
    if(k_ > k or i == -1 or j== -1){
        return -10000;
    }
    if(memo[i][j][k_] != -1){
        return  memo[i][j][k_];
    }
    int res= -10000;
    if(a[i] == b[j]){
        res = max(res,f(i-1,j-1,k_+1) + (int) a[i]);
        res = max(res,f(i-1,j-1,k_));
    }
    res = max(res,f(i-1,j,k_));
    res = max(res,f(i,j-1,k_));

    return memo[i][j][k_] =res;
}
int main() {
    int t;
    cin >> t;
    while(t--){
        cin >> a >> b;
        cin  >> k;
        for (int i = 0; i < 102; i++) {
            for (int j = 0; j < 102; j++) {
                for (int l = 0; l < 102; l++) {
                    memo[i][j][l] = -1;
                }
            }
        }
        int r = f((int) a.size() - 1, (int) b.size() - 1, 0);
        if(r < 0) {
            cout << 0 << endl;
        }
        else {
            cout << r << endl;
        }
    }
}