#include <bits/stdc++.h>
using namespace std;

ifstream fin("seif.in");
ofstream fout("seif.out");

const int MAX = 1000;
int dp[MAX + 1][MAX + 1];
int nextA[MAX + 1][26];
int nextB[MAX + 1][26];

int main() {
    int t; fin >> t;
    while (t--) {
        int k; fin >> k;
        string a; fin >> a; int m = a.size();
        string b; fin >> b; int n = b.size();

        memset(dp, 0, sizeof(dp));
        for (int i = m - 1; i >= 0; i--)
            for (int j = n - 1; j >= 0; 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]);

        memset(nextA, m, sizeof(nextA));
        for (int i = m - 1; i >= 0; i--) {
            for (int x = 0; x < 26; x++)
                nextA[i][x] = nextA[i + 1][x];
            nextA[i][a[i] - 'A'] = i;
        }
        memset(nextB, n, sizeof(nextB));
        for (int j = n - 1; j >= 0; j--) {
            for (int x = 0; x < 26; x++)
                nextB[j][x] = nextB[j + 1][x];
            nextB[j][b[j] - 'A'] = j;
        }

        for (int i = 0, j = 0; k >= 0 || (i <= m && j <= n); k--) {
            bool ok = false;
            for (int x = 25; x >= 0; x--)
                if (nextA[i][x] < m && nextB[j][x] < n && dp[nextA[i][x]][nextB[j][x]] >= k) {
                    i = nextA[i][x] + 1;
                    j = nextB[j][x] + 1;
                    fout << (char) (x + 'A');
                    ok = true;
                    break;
                }
            if (!ok)
                break;
        }
        fout << '\n';
    }

    fout.close();
    return 0;
}