#include <stdio.h>
#include <string.h>

#define max(i,j) ((i) > (j) ? (i) : (j))
#define nmax 1005
#define sigma 26

int n, m, T, k, c[nmax][nmax], leng;
int lasta, lastb, posa[nmax][sigma], posb[nmax][sigma];
char ch, a[nmax], b[nmax];

void solve()
{
	leng = 0;
	memset(posa, 0, sizeof(posa));
	memset(posb, 0, sizeof(posb));
	for(int i = n; i >= 1; i--)
	{
		for(int j = 0; j < sigma; j++) posa[i][j] = posa[i + 1][j];
		posa[i][a[i] - 'A'] = i;
	}

	for(int i = m; i >= 1; i--)
	{
		for(int j = 0; j < sigma; j++) posb[i][j] = posb[i + 1][j];
		posb[i][b[i] - 'A'] = i;
	}

	for(int i = n; i >= 1; i--)
		for(int j = m; j >= 1; j--)
		{
			if(a[i] == b[j]) c[i][j] = 1 + c[i + 1][j + 1];
			else c[i][j] = max(c[i][j + 1], c[i + 1][j]);
		}

	lasta = lastb = 0;
	for(int i = 1; i <= n; i++)
		for(int lit = sigma - 1; lit >= 0; lit--)
		{
			int nexta = posa[lasta + 1][lit], nextb = posb[lastb + 1][lit];
			if(nexta != 0 && nextb != 0 && c[nexta][nextb] >= k - i + 1)
			{
				lasta = nexta, lastb = nextb, printf("%c", 'A' + lit);
				break;
			}
		}
	printf("\n");
}

int main()
{
	freopen("seif.in", "r", stdin);
	freopen("seif.out", "w", stdout);

	for(scanf("%d\n", &T); T; T--)
	{
		scanf("%d\n", &k); n = m = 0;
		while(1)
		{
			scanf("%c", &ch);
			if(ch >= 'A' && ch <= 'Z') a[++n] = ch;
			else break;
		}
		while(1) 
		{
			scanf("%c", &ch);
			if(ch >= 'A' && ch <= 'Z') b[++m] = ch;
			else break;
		}
		solve();
	}

	return 0;
}