#include <fstream>
#include <cstring>

using namespace std;

ifstream cin("seif.in");
ofstream cout("seif.out");

const int MAXN = 1000;
const int SIGMA = 26;

char a[1 + MAXN], b[1 + MAXN];

int dp[1 + MAXN][1 + MAXN];
int previousA[1 + MAXN][SIGMA], previousB[1 + MAXN][SIGMA];

int main() {
    int tests;
    cin >> tests;
    for (int test = 1; test <= tests; test++) {
        int k;
        cin >> k;
        cin >> a + 1 >> b + 1;
        int n = strlen(a + 1), m = strlen(b + 1);
        for (int i = n; i >= 1; i--)
            for (int j = m ; j >= 1; j--)
                if (a[i] == b[j])
                    dp[i][j] = dp[i + 1][j + 1] + 1;
                else
                    dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
        for (int i = n; i >= 1; i--) {
            for (int j = 0; j < SIGMA; j++)
                previousA[i][j] = previousA[i + 1][j];
            previousA[i][a[i] - 'A'] = i;
        }
        for (int i = m; i >= 1; i--) {
            for (int j = 0; j < SIGMA; j++)
                previousB[i][j] = previousB[i + 1][j];
            previousB[i][b[i] - 'A'] = i;
        }
        for (int i = 1, j = 1; k >= 0 || (i <= n && j <= m); k--) {
            int ch;
            for (ch = SIGMA - 1; ch >= 0; ch--)
                if (previousA[i][ch] && previousB[j][ch] && dp[previousA[i][ch]][previousB[j][ch]] >= k) {
                    cout << char(ch + 'A');
                    i = previousA[i][ch] + 1;
                    j = previousB[j][ch] + 1;
                    break;
                }
            if (ch == -1)
                break;
        }
        cout << "\n";
    }
    return 0;
}