#include <stdio.h>
#include <string.h>
int check[1002][1002] = { {0,}, };
int main(void)
{
int test_case;
scanf("%d\n", &test_case);
for (int z = 1; z<= test_case; z++) {
for (int i = 0; i < 1002; i++)
for (int j = 0; j < 1002; j++)
check[i][j] = 0;
char str1[1001] = { 0, };
char str2[1001] = { 0, };
scanf("%s", str1);
scanf("%s", str2);
int len1 = strlen(str1);
int len2 = strlen(str2);
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (str1[i - 1] == str2[j - 1]) {
check[i][j] = check[i - 1][j - 1] + 1;
}
else {
check[i][j] = (check[i - 1][j] >= check[i][j - 1]) ? check[i - 1][j] : check[i][j - 1];
}
}
}
printf("#%d %d\n", z, check[len1][len2]);
}
return 0;
}