#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>

using namespace std;
struct wyraz
{
    string wyraz;
};

int podciag(wyraz  * sek1, wyraz * sek2, int dl_wyr1, int dl_wyr2)
{
    int **tab = new int * [dl_wyr2+1];
    for (int i = 0 ; i <= dl_wyr2 ; i++)
    {
        tab[i] = new int [dl_wyr1+1];
    }
    for(int i = 0; i<=dl_wyr2; i++)
    {
        for (int j = 0; j <= dl_wyr1; j++)
        {
            tab[i][j] = 0;//wypełniam całą tablicę zerami w tym najważniejsy pierwzy wiersz i pierwsza kolumne
        }
    }
    for(int i=1; i<=dl_wyr1; i++)
    {
        for(int j=1; j<=dl_wyr2; j++)
        {
            if(sek1[1].wyraz[i]==sek2[1].wyraz[j])
            {
                tab[j][i] = tab[j-1][i-1]+1;
            }
            else
            {
                if(tab[j-1][i]>=tab[j][i-1])
                {
                    tab[j][i]=tab[j-1][i];
                }
                else
                {
                    tab[j][i] = tab[j][i-1];
                }
            }
        }
    }
    return tab[dl_wyr2][dl_wyr1];
}
int main()
{
    fstream in;
    ofstream out;
    string lin;
    string wyraz1;
    int n,licz=0;
    in.open("In0301.txt",ios::in);
    in >>n;
    wyraz * sekwencja = new wyraz [2*n];
    wyraz * sekwencja1 = new wyraz[n];
    wyraz * sekwencja2 = new wyraz[n];
    for (int i =0 ; i <=2*n; i++)
    {
        getline(in,lin);
        istringstream zmienna(lin);
        while (zmienna >> wyraz1)
        {
            sekwencja[licz].wyraz = wyraz1;
            licz++;
        }
    }
    licz=0;
    for(int i=0; i<2*n; i++) //utworzenie dwóch tablic w celu rozdzielenia i porównywania
    {
        sekwencja1[licz] = sekwencja[i];
        i++;
        sekwencja2[licz] = sekwencja[i];
        licz++;
    }
    out.open("Out0301.txt",ios::out);
    for(int i = 0; i<n ; i++)
    {
        int dl1=sekwencja1[i].wyraz.length();
        int dl2=sekwencja2[i].wyraz.length();
        if(out.good() == true)
        {
            out << podciag(sekwencja1,sekwencja2,dl1,dl2)<<" ";
        }

    }
    return 0;
}