stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)



vector<vector<int> > DP(1000,vector<int>(1000));



void init(int n,int m){

    rep(i,n){

        rep(j,m){DP[i][j]=-1;}

    }

}



int LCS(char a[],char b[],int n,int m){

    if(n<0||m<0)return 0;

    if(DP[n][m]!=-1)return DP[n][m];

    if(a[n]==b[m])return DP[n][m]=1+LCS(a,b,n-1,m-1);

    return DP[n][m]=max(LCS(a,b,n-1,m),LCS(a,b,n,m-1));

}



int main(){

    int q;cin>>q;

    char s[1001],t[1001];

    rep(i,q){

        cin>>s>>t;

        int n=strlen(s),m=strlen(t);

        init(n,m);

        int ans=LCS(s,t,n-1,m-1);

        printf("%d\n",ans);

    }

}


// Faster C++ solution for the same problem (measured speedup: 5.240501593861254x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)



int LCS(string a,string b){

    int n1=a.size(),n2=b.size();

    int DP[n1+1][n2+1];

    DP[0][0]=0;

    rep(i,n1)DP[i+1][0]=0;

    rep(i,n2)DP[0][i+1]=0;

    rep(i,n1){

        rep(j,n2){

            if(a[i]==b[j])DP[i+1][j+1]=1+DP[i][j];

            else DP[i+1][j+1]=max(DP[i][j+1],DP[i+1][j]);

        }

    }

    return DP[n1][n2];

}



int main(){

    int q;cin>>q;

    string s,t;

    rep(i,q){

        cin>>s>>t;

        int ans=LCS(s,t);

        printf("%d\n",ans);

    }

}
// Slower C++ solution:
#include<iostream>

#include<stdio.h>

#include<string.h>

#include<algorithm>

using namespace std;

static const int N=1000;

int lcs(string X,string Y)

{

    int c[N+1][N+1];

    int m=X.size();

    int n=Y.size();

    int maxl=0;

    X=" "+X;

    Y=" "+Y;

    for(int i=0;i<=m;i++)c[i][0]=0;

    for(int j=0;j<=n;j++)c[0][j]=0;



      for(int i=1;i<=m;i++)

      {

          for(int j=1;j<=n;j++)

          {

              if(X[i]==Y[j])

                 {

                     c[i][j]=c[i-1][j-1]+1;

                 }

                    else{

                        c[i][j]=max(c[i-1][j],c[i][j-1]);

                }

                    maxl=max(maxl,c[i][j]);

          }

      }

      return maxl;

}

int main()

{

    string s1,s2;

    int n;

    cin>>n;

    for(int i=0;i<n;i++)

    {

        cin>>s1>>s2;

        cout<<lcs(s1,s2)<<endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.776799266382428x):
#include <stdio.h>

#include <string.h>

#define N 1010

char a[N];

char b[N];

int dp[N][N];

//int LCS(int i, int j){

//    if(i == -1 || j == -1) return 0;

//    if(a[i] == b[j]) return LCS(i-1, j-1) + 1;

//    else return LCS(i-1, j) > LCS(i, j-1) ? LCS(i-1, j) : LCS(i, j-1);

//}

int main(){

    int k;

    scanf("%d", &k);

    while(k--){

        scanf("%s", a);

        scanf("%s", b);

        int n = strlen(a);

        int m = strlen(b);

        for(int i = n-1; i >= 0; i--) a[i+1] = a[i];

        for(int i = m-1; i >= 0; i--) b[i+1] = b[i];

        int max = n > m ? n : m;

        for(int i = 0; i <= max; i++) dp[0][i] = dp[i][0] = 0;

        for(int i = 1; i <= n; i++){

            for(int j = 1; j <= m; j++){

                if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;

                else {

                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];

                }

            }

        }

        printf("%d\n", dp[n][m]);

        //printf("%d\n", LCS(strlen(a)-1, strlen(b)-1));

    }

    return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <iostream>

#include <cmath>

#include <algorithm>

#include <cstring>

using namespace std;



const int maxn = 1000 + 5;

int dp[maxn][maxn];

char x[maxn];

char y[maxn];



int main()

{

    int q;

    scanf("%d", &q);

    while (q--)

    {

        scanf("%s %s", x + 1, y + 1);

        memset(dp, 0, sizeof(dp));

        int m = strlen(x + 1);

        int n = strlen(y + 1);

        for (int i = 1; i <= m; i++)

            for (int j = 1; j <= n; j++)

            {

                if (x[i] == y[j])

                    dp[i][j] = dp[i-1][j-1] + 1;

                else

                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

            }

        printf("%d\n", dp[m][n]);

    }

    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 70.28011613430913x):
#include <stdio.h>

#include <string.h>

#define N 1010

char a[N];

char b[N];

int dp[N][N];

//int LCS(int i, int j){

//    if(i == -1 || j == -1) return 0;

//    if(a[i] == b[j]) return LCS(i-1, j-1) + 1;

//    else return LCS(i-1, j) > LCS(i, j-1) ? LCS(i-1, j) : LCS(i, j-1);

//}

int main(){

    int k;

    scanf("%d", &k);

    while(k--){

        scanf("%s", a);

        scanf("%s", b);

        int n = strlen(a);

        int m = strlen(b);

        for(int i = n-1; i >= 0; i--) a[i+1] = a[i];

        for(int i = m-1; i >= 0; i--) b[i+1] = b[i];

        int max = n > m ? n : m;

        for(int i = 0; i <= max; i++) dp[0][i] = dp[i][0] = 0;

        for(int i = 1; i <= n; i++){

            for(int j = 1; j <= m; j++){

                if(a[i] == b[j]) dp[i][j] = dp[i-1][j-1] + 1;

                else {

                    dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];

                }

            }

        }

        printf("%d\n", dp[n][m]);

        //printf("%d\n", LCS(strlen(a)-1, strlen(b)-1));

    }

    return 0;

}
// Slower C++ solution:
#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<stack>

#include<queue>

#include<vector>

#include<algorithm>

#include<string>

#include<iostream>

using namespace std;

static const int N=1000;

/*int max(int a,int b){

    if(a>b)return a;else return b;

}*/

int lcs(string X,string Y){

    int c[N+1][N+1];

    int m=X.size();

    int n=Y.size();

    int maxl=0;

    X=' '+X;

    Y=' '+Y;

    for(int i=0;i<=m;i++)c[i][0]=0;

    for(int j=1;j<=n;j++)c[0][j]=0;

    

    for(int i=1;i<=m;i++){

        for(int j=1;j<=n;j++){

            if(X[i]==Y[j]){

                c[i][j]=c[i-1][j-1]+1;

            }else{

                c[i][j]=max(c[i-1][j],c[i][j-1]);

            }

            maxl=max(maxl,c[i][j]);

        }

    }

    return maxl;

}



int main(){

    string s1,s2;

    int n;cin>>n;

    for(int i=0;i<n;i++){

        cin>>s1>>s2;

        cout<<lcs(s1,s2)<<endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.1137140590351056x):




#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<stack>

#include<queue>

#include<vector>

#include<algorithm>

#include<string>

#include<iostream>

using namespace std;

typedef long long ll;

int mod(ll a){

    int c=a%1000000007;

    if(c>=0)return c;

    else return c+1000000007;

}

typedef pair<int,int> i_i;





int main(){

    int q;cin>>q;

    while(q){

        char s[1005],t[1005];cin>>s>>t;

        ll ls=strlen(s),lt=strlen(t);

        for(ll i=ls-1;i>=0;i--)s[i+1]=s[i];

        for(ll j=lt-1;j>=0;j--)t[j+1]=t[j];

        int dp[ls+1][lt+1];

        for(int i=0;i<=ls;i++)dp[i][0]=0;

        for(int j=0;j<=lt;j++)dp[0][j]=0;

        for(int i=1;i<=ls;i++){

            for(int j=1;j<=lt;j++){

                if(s[i]==t[j])dp[i][j]=dp[i-1][j-1]+1;

                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

            }

        }

        cout<<dp[ls][lt]<<endl;

        q--;

    }

    

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int dp[1002][1002];



int main(){

	int n;cin >> n;

	string x, y;

	while(n--){

		fill((int*)dp, (int*)(dp+1002), 0);

		cin >> x >> y;

		for(int i = 1;i <= x.size();i++){

			for(int j = 1;j <= y.size();j++){

				if(x[i-1] == y[j-1])dp[i][j] = dp[i-1][j-1] + 1;

				else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

			}

		}

		cout << dp[x.size()][y.size()] << endl;

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 13.435224500671527x):
#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int dp[1002][1002];



int main(){

	int n;cin >> n;

	string x, y;

	while(n--){

		cin >> x >> y;

		for(int i = 1;i <= x.size();i++){

			for(int j = 1;j <= y.size();j++){

				if(x[i-1] == y[j-1])dp[i][j] = dp[i-1][j-1] + 1;

				else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

			}

		}

		cout << dp[x.size()][y.size()] << endl;

	}

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

#include <string>

#include <cmath>

#include <set>

#include <algorithm>

#include <array>

#include <complex>

#include <utility>

#include <map>

#include <inttypes.h>



int LCS(std::string s, std::string t){

    int n, m, c[1001][1001] = {0};

    n = s.size();

    m = t.size();

    int maxlen = 0;

    for(int i = 1; i <= n; i++){

        c[i][0] = 0;

    }

    for(int i = 1; i <= m; i++){

        c[0][i] = 0;

    }

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= m; j++){

            if(s[i - 1] == t[j - 1]){

                c[i][j] = c[i - 1][j - 1] + 1;

            }

            else{

                c[i][j] = std::max(c[i - 1][j], c[i][j - 1]);

            }

            maxlen = std::max(maxlen, c[i][j]);

        }

    }

    return maxlen;

}

int main(){

    int N;



    std::cin >> N;

    std::string s1, s2;

    for(int i = 0; i<N; i++){

        std::cin >> s1 >> s2;

        std::cout << LCS(s1, s2) << std::endl;

    }

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 13.432605933196614x):
#include <iostream>

#include <vector>

#include <string>

#include <cmath>

#include <set>

#include <algorithm>

#include <array>

#include <complex>

#include <utility>

#include <map>

#include <inttypes.h>

int c[1001][1001] = {0};

/*int LCS(std::string s, std::string t){

    int n, m, c[1001][1001] = {0};

    n = s.size();

    m = t.size();

    int maxlen = 0;

    for(int i = 1; i <= n; i++){

        c[i][0] = 0;

    }

    for(int i = 1; i <= m; i++){

        c[0][i] = 0;

    }

    for(int i = 1; i <= n; i++){

        for(int j = 1; j <= m; j++){

            if(s[i - 1] == t[j - 1]){

                c[i][j] = c[i - 1][j - 1] + 1;

            }

            else{

                c[i][j] = std::max(c[i - 1][j], c[i][j - 1]);

            }

            maxlen = std::max(maxlen, c[i][j]);

        }

    }

    return maxlen;

}*/

int main(){

    int N;



    std::cin >> N;

    std::string s1, s2;

    for(int i = 0; i<N; i++){

        std::cin >> s1 >> s2;

        int n, m;

        n = s1.size();

        m = s2.size();

        int maxlen = 0;

        for(int i = 1; i <= n; i++){

            c[i][0] = 0;

        }

        for(int i = 1; i <= m; i++){

            c[0][i] = 0;

        }

        for(int i = 1; i <= n; i++){

            for(int j = 1; j <= m; j++){

                if(s1[i - 1] == s2[j - 1]){

                    c[i][j] = c[i - 1][j - 1] + 1;

                }

                else{

                    c[i][j] = std::max(c[i - 1][j], c[i][j - 1]);

                }

                maxlen = std::max(maxlen, c[i][j]);

            }

        }

        std::cout << maxlen << std::endl;

    }

    return 0;

}
// Slower C++ solution:
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>

#include <cstdlib>

#include <string>

#include <iostream>

#include <queue>



using namespace std;



const char *X, *Y;

int X_length, Y_length;

bool alreadySeenTable[256];

int table_lcs[1001][1001];



int lcs(int x_begin, int y_begin) {

	int i, j, to;

	int max = 0;

	int v_lcs;

	

	if (table_lcs[x_begin][y_begin] != -1) {

		return table_lcs[x_begin][y_begin];

	}

	

	for (i = 0; i < 256; i++) {

		alreadySeenTable[i] = false;

	}

	i = x_begin;

	j = y_begin;

	to = Y_length-1;

	while(i <= X_length-1) {

		bool found = false;

		while (j <= to) {

			if (X[i] == Y[j]) {

				v_lcs = lcs(i + 1, j + 1) + 1;

				if (v_lcs > max) {

					max = v_lcs;

				}

				found = true;

				break;

			}

			else {

				j++;

			}

		}

		if (found == false) {

			i++;

			j = y_begin;

		}

		else {

			i++;

			to = j - 1;

			j = y_begin;

		}

	}

	return table_lcs[x_begin][y_begin] = max;

}



int main() {



	int N;

	cin >> N;

	string stringX, stringY;



	for (int i = 1; i <= N; i++) {

		for (int i = 0; i < 1001; i++) {

			for (int j = 0; j < 1001; j++) {

				table_lcs[i][j] = -1;

			}

		}

		cin >> stringX >> stringY;

		X = stringX.c_str();

		X_length = stringX.size();

		Y = stringY.c_str();

		Y_length = stringY.size();

		printf("%d\n", lcs(0, 0));

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 13.342493664541113x):
#include <iostream>

#include <string>

#include <algorithm>

using namespace std;



int lengthOfLcs_r(const char x[], const char y[], int ix, int iy, int xsize, int ysize, int **lengthTable) {

	if (ix == xsize || iy == ysize) {

		return 0;

	}

	if (lengthTable[ix][iy] != -1) {

		return lengthTable[ix][iy];

	}

	if (x[ix] == y[iy]) {

		return lengthTable[ix][iy] = lengthOfLcs_r(x, y, ix + 1, iy + 1, xsize, ysize, lengthTable) + 1;

	}

	return lengthTable[ix][iy] = max(lengthOfLcs_r(x, y, ix, iy + 1, xsize, ysize, lengthTable), lengthOfLcs_r(x, y, ix + 1, iy, xsize, ysize, lengthTable));

}



int lengthOfLcs(string x, string y) {

	int xsize = x.size(), ysize = y.size();



	int **lengthTable = new int*[xsize];

	for (int i = 0; i < xsize; ++i) {

		lengthTable[i] = new int[ysize];

		fill_n(lengthTable[i], ysize, -1);

	}



	int ret = lengthOfLcs_r(x.c_str(), y.c_str(), 0, 0, xsize, ysize, lengthTable);

	

	for (int i = 0; i < xsize; i++) {

		delete[] lengthTable[i];

	}

	delete[] lengthTable;

	

	return ret;

}



int main() {

	int q;

	string x, y;



	cin >> q;

	for (int i = 0; i < q; ++i) {

		cin >> x >> y;

		cout << lengthOfLcs(x, y) << endl;

	}

	return 0;

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

using namespace std;



#define N 1000



int lcs(string X,string Y){

	int c[N+1][N+1];

	int m = X.size();

	int n = Y.size();

	X = ' ' + X;

	Y = ' ' + Y;

	for(int i=0;i<=m;i++)c[i][0]=0;

	for(int i=1;i<=n;i++)c[0][i]=0;

	for(int i=1;i<=m;i++){

		for(int j=1;j<=n;j++){

			if(X[i]==Y[j]){

				c[i][j] = c[i-1][j-1]+1;

			}else if(c[i][j-1]>=c[i-1][j]){

				c[i][j] = c[i][j-1];

			}else{

				c[i][j] = c[i-1][j];

			}

		}

	}

	return c[m][n];

}



int main(){

	int n;

	string X,Y;

	cin >> n;

	for(int i=0;i<n;i++){

		cin >> X >> Y;

		printf("%d\n",lcs(X,Y));

	}

	return 0;

}




// Faster C++ solution for the same problem (measured speedup: 1.1096026417167617x):
#include <cstdio>

#include <cstdlib>

#include <algorithm>

#include <cstring>

#include <queue>

#include <vector>

#include <functional>

#include <map>

#include <set>

#include <cmath>

#include <string>

#define SIZE 200005

#define INF 1000000005LL



#include<iostream>



using namespace std;

typedef long long int ll;

typedef pair <int,int> P;



static const int N = 1005;



int n;

ll K;

int dp[N][N];



int main()

{

	scanf("%d",&n);

	string s1,s2;

	for(int k=0;k<n;k++){

		//scanf("%s",&s1);

		//scanf("%s",&s2);

		cin >> s1 >> s2;

		s1 = ' ' + s1;

		s2 = ' ' + s2;

		for(int i=0;i<s1.size();i++)dp[i][0]=0;

		for(int i=0;i<s2.size();i++)dp[0][i]=0;

		for(int i=1;i<s1.size();i++){

			for(int j=1;j<s2.size();j++){

				if(s1[i]==s2[j]){

					dp[i][j] = dp[i-1][j-1]+1;

				}else{

					dp[i][j] = max(dp[i-1][j],dp[i][j-1]);

				}

				//printf("%d\n",dp[i][j]);

			}

		}

		printf("%d\n",dp[s1.size()-1][s2.size()-1]);

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <string>

#include <utility>

#include <algorithm>

#include <vector>

#include <cstdio>

#include <cstring>



using namespace std;



string s1,s2;

int l[1010][1010];

bool flag[1010][1010];



int L(int i,int j){

	//cout<<i<<" "<<j<<endl;

	if(i<0||j<0){

		return 0;

	}

	else if(s1.at(i)==s2.at(j)){

		if(!flag[i][j]){

			l[i][j]=1+L(i-1,j-1);

			flag[i][j]=true;

		}

		return l[i][j];

	}

	else{

		if(!flag[i][j]){

			int a=L(i,j-1);

			int b=L(i-1,j);

			l[i][j]=a>b?a:b;

			flag[i][j]=true;

		}

		return l[i][j];

	}

}



int main(){

	int q;

	cin>>q;

	for(int i=0; i<q; i++){

		cin>>s1>>s2;

		for(int j=0; j<1010; j++){

			for(int k=0; k<1010; k++){

				flag[j][k]=false;

			}

		}



		cout<<L(s1.size()-1,s2.size()-1)<<endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 2.2385473229926123x):
#include <bits/stdc++.h>

using namespace std;

#define rep(i,n) REP(i,0,n)

#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)

#define repr(i, n) REPR(i, n, 0)

#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)

#define pb push_back

#define all(r) r.begin(),r.end()

#define rall(r) r.rbegin(),r.rend()

#define fi first

#define se second



typedef long long ll;

typedef vector<int> vi;

typedef vector<ll> vl;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;



const ll INF = 1e18;

const ll MOD = 1e9 + 7;

const double EPS = 1e-8;



template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}

template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}



void solve() {

    string s, t;

    cin >> s >> t;

    int n = s.size(), m = t.size();

    vector<vi> dp(n+2, vi(m+2));

    rep(i, n+1) rep(j, m+1) {

        // cout << i << " " << j << endl;

        if(i >= n) {

            chmax(dp[i][j+1], dp[i][j]);

        }

        else if(j >= m) {

            chmax(dp[i+1][j], dp[i][j]);

        }

        else if(s[i] == t[j]) chmax(dp[i+1][j+1], dp[i][j]+1);

        else {

            chmax(dp[i+1][j], dp[i][j]);

            chmax(dp[i][j+1], dp[i][j]);

        }

    }

    cout << dp[n][m] << '\n';

    // rep(i, n+2) {

    //     rep(j, m+2) {

    //         cout << " " << dp[i][j];

    //     }

    //     cout << endl;

    // }

}



int main(){

    cin.tie(0);

    ios::sync_with_stdio(false);

    int n;

    cin >> n;

    rep(i, n) solve();

    return 0;

}
// Slower C++ solution:
#include <cassert>

#include <algorithm>

#include <iostream>

#include <vector>

#include <string>



class TLcsSolver

{

    typedef std::vector<std::vector<int> > TTable;

    TTable FTable;

    std::string FArray1;

    std::string FArray2;



    int Count(int i, int j)

    {

        if(i == 0 || j == 0) return 0;

        if(FArray1[i-1] == FArray2[j-1]){

            return FTable[i-1][j-1] + 1;

        }

        return std::max(FTable[i-1][j], FTable[i][j-1]);

    }

    void Solve()

    {

        for(std::size_t i = 1; i < FTable.size(); ++i){

            for(std::size_t j = 1; j < FTable[i].size(); ++j){

                FTable[i][j] = Count(i, j);

            }

        }

    }

public:

    TLcsSolver(const std::string& a, const std::string& b)

     : FArray1(a), FArray2(b)

     , FTable(a.size()+1, std::vector<int>(b.size()+1, 0))

    {

        Solve();

        // Print();

    }

    int Answer()const

    {

        return FTable[FArray1.size()][FArray2.size()];

    }

    void Print()const

    {

        for(std::size_t i = 0; i < FTable.size(); ++i){

            for(std::size_t j = 0; j < FTable[i].size(); ++j){

                std::cout << FTable[i][j] << '\t';

            }

            std::cout << '\n';

        }

    } 

};



int main()

{

    int n;

    std::cin >> n;

    for(int i = 0; i < n; ++i){

        std::string a, b;

        std::cin >> a >> b;

        std::cout << TLcsSolver(a, b).Answer() << std::endl;

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 3.574112670874215x):
#include <cstdio>

#include <cstring>

#include <algorithm>



#define SIZE 1010

class TLcsSolver

{

    int FTable[SIZE][SIZE];

    const char* FArray1;

    const char* FArray2;

    const int Fn1;

    const int Fn2;



    int Count(int i, int j)

    {

        if(i == 0 || j == 0) return 0;

        if(FArray1[i-1] == FArray2[j-1]){

            return FTable[i-1][j-1] + 1;

        }

        return std::max(FTable[i-1][j], FTable[i][j-1]);

    }

    void Solve()

    {

        for(std::size_t i = 1; i < Fn1; ++i){

            for(std::size_t j = 1; j < Fn2; ++j){

                FTable[i][j] = Count(i, j);

            }

        }

    }

    void Print()const

    {

        for(std::size_t i = 0; i < Fn1; ++i){

            for(std::size_t j = 0; j < Fn2; ++j){

                printf("%d\t", FTable[i][j]);

            }

            printf("\n");

        }

    } 

public:

    TLcsSolver(const char* a, const char* b)

     : FArray1(a), FArray2(b)

     , Fn1(std::strlen(a)), Fn2(std::strlen(b))

    {

        Solve();

        // Print();

    }

    int Answer()const

    {

        return FTable[Fn1-1][Fn2-1];

    }

};



int main()

{

    int n;

    std::scanf("%d\n", &n);

    char a[SIZE];

    char b[SIZE];

    for(int i = 0; i < n; ++i){

        std::fgets(a, SIZE, stdin);

        std::fgets(b, SIZE, stdin);

        std::printf("%d\n", TLcsSolver(a, b).Answer());

    }

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long int

#define sz  200010

using namespace std;





string ss[sz];



int main()

{





    string x="";



    ll h,w,i,j,k,p,a,b;



    cin>>h>>w;



    for(i=1; i<=h; i++)cin>>ss[i];



    for(i=1; i<=w+2; i++)x+="#";



    cout<<x<<endl;

    for(i=1; i<=h; i++)

    {

        cout<<"#"<<ss[i]<<"#"<<endl;

    }

    cout<<x<<endl;







    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 8.15484717770116x):
#include<bits/stdc++.h>

using namespace std;

#define LL long long int

#define DL double

#define MLL map<LL,LL>::iterator

#define MSL map<string,L>::iterator

#define MLS map<LL,string>::iterator

#define MSS map<string,string>::iterator

#define MCL map<char,LL>::iterator

#define SL set<LL>::iterator

#define SS set<string>::iterator sl

#define G getline

#define SZ size()

#define IN insert

#define C clear()

#define B begin()

#define F front()

#define T top()

#define E end()

#define EM empty()

#define V vector

#define Q queue

#define DQ deque

#define PQ priority_queue

#define ST stack

#define FI first

#define SE second

#define PI acos(-1)

#define PS push

#define PP pop()

#define PSF push_front

#define PSB push_back

#define PPF pop_front()

#define PPB pop_back()

#define endl "\n"

#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int main()

{

    FAST;

    LL n,m,i,j,k,p,q,o,l,s,t,z;

    string a;

    cin>>n>>m;

    for(i=0; i<m+2; i++)

    {

        cout<<"#";

    }

    cout<<endl;

    for(i=0; i<n; i++)

    {

        cin>>a;

        cout<<"#"<<a<<"#"<<endl;;

    }

    for(i=0; i<m+2; i++)

    {

        cout<<"#";

    }

    cout<<endl;

}
// Slower C++ solution:
#include<bits/stdc++.h>

#define ll long long int

#define sz  200010

using namespace std;





string ss[sz];



int main()

{





    string x="";



    ll h,w,i,j,k,p,a,b;



    cin>>h>>w;



    for(i=1; i<=h; i++)cin>>ss[i];



    for(i=1; i<=w+2; i++)x+="#";



    cout<<x<<endl;

    for(i=1; i<=h; i++)

    {

        cout<<"#"<<ss[i]<<"#"<<endl;

    }

    cout<<x<<endl;







    return 0;

}




// Faster C++ solution for the same problem (measured speedup: 8.268876794709765x):
#include <bits/stdc++.h>

#include <string.h>  

#include <iostream>  

#include <map>  

#include <utility>  

using namespace std;



int main()

{

    int h, w;

    cin >> h >> w;

    string s;

    for(int i = 0; i < w+2; i++)

    cout << "#";

    cout << "\n";

    for(int i = 0; i < h; i++)

    {

        cin >> s;

        cout << "#";

        cout << s;

        cout << "#\n";



    }

   

    for(int i = 0; i < w+2; i++)

    cout << "#";

    

}