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

int n, m, t, k;
int d[1005][1005];
int pred1[1005][28], pred2[1005][28];
char s1[1005], s2[1005];

inline int max (int a, int b) {return a > b ? a : b;}

int main ()
{
	freopen ("seif.in", "r", stdin);
	freopen ("seif.out", "w", stdout);
	
	scanf ("%d", &t);
	
	int i, j, l;
	
	while (t --)
	{
		memset (d, 0, sizeof (d));
		memset (pred1, 0, sizeof (pred1));
		memset (pred2, 0, sizeof (pred2));
		
		scanf ("%d\n", &k);
		gets (s1 + 1);
		gets (s2 + 1);
		
		n = strlen (s1 + 1);
		m = strlen (s2 + 1);
		
		for (i = n; i >= 1; i --)
			for (j = m; j >= 1; j --)
				if (s1[i] == s2[j])
					d[i][j] = d[i + 1][j + 1] + 1;
				else
					d[i][j] = max (d[i + 1][j], d[i][j + 1]);
		
		for (i = n; i >= 1; i --)
			for (j = 0; j < 26; j ++)
				if (s1[i] - 'A' == j)
					pred1[i][j] = i;
				else
					pred1[i][j] = pred1[i + 1][j];
		for (i = m; i >= 1; i --)
			for (j = 0; j < 26; j ++)
				if (s2[i] - 'A' == j)
					pred2[i][j] = i;
				else
					pred2[i][j] = pred2[i + 1][j];
		
		i = j = 1;
		for (; k >= 0 || (i <= n && j <= n); k --)
		{
			for (l = 25; l >= 0; l --)
				if (pred1[i][l] && pred2[j][l] && d[pred1[i][l]][pred2[j][l]] >= k)
				{
					printf ("%c", l + 'A');
					i = pred1[i][l] + 1;
					j = pred2[j][l] + 1;
					break;
				}
			if (k < 0)
				break;
		}
		printf ("\n");
	}
	return 0;
}