#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ull;
char *str1, *str2;
ull F1[10001], F2[10001];
int L1, L2;
ull Base[10001];
const ull B = 100000007;

bool Judge(int mid){
    for(int i = 0, j = i + mid; j <= L1; i ++, j ++){
        ull t = F1[j] - F1[i] * Base[mid];
        for(int l = 0, r = l + mid; r <= L2; l ++, r ++){
            ull nt = F2[r] - F2[l] * Base[mid];
            if(nt == t){
                return true;
            }
        }
    }
    return false;
}

int main(){
    Base[0] = 1;
    for(int i = 1; i <= 10000; i ++){
        Base[i] = Base[i - 1] * B;
    }
    str1 = new char[10001];
    str2 = new char[10001];
    int Num;
    scanf("%d", &Num);
    getchar();
    for(int num = 0; num < Num; num ++){
        gets(str1);
        gets(str2);
        L1 = strlen(str1);
        L2 = strlen(str2);
        if(L2 < L1){
            swap(L1, L2);
            swap(str1, str2);
        }
        F1[0] = 0;
        for(int i = 1; i <= L1; i ++){
            F1[i] = F1[i - 1] * B + str1[i - 1];
        }
        F2[0] = 0;
        for(int i = 1; i <= L2; i ++){
            F2[i] = F2[i - 1] * B + str2[i - 1];
        }
        int lb = 0, ub = L1;
        int ans = 0;
        while(ub >= lb){
            int mid = (ub + lb) >> 1;
            if(Judge(mid)){
                ans = mid;
                lb = mid + 1;
            } else {
                ub = mid - 1;
            }
        }
        printf("Nejdelsi spolecny retezec ma delku %d.\n", ans);
    }
}