Go: package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const N = 1001

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func lcs(x, y string) int {
	var c [N][N]int
	m := len(x)
	n := len(y)
	var maxl int

	x = " " + x
	y = " " + y

	for i := 1; i <= m; i++ {
		for 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
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	q, _ := strconv.Atoi(sc.Text())

	var out bytes.Buffer
	for i := 0; i < q; i++ {
		sc.Scan()
		s1 := sc.Text()
		sc.Scan()
		s2 := sc.Text()
		out.WriteString(fmt.Sprintf("%d\n", lcs(s1, s2)))
	}
	return strings.TrimRight(out.String(), "\n")
}

func main() {
	fmt.Println(answer(os.Stdin))
}

C++: #include <iostream>
#include <cstring>

using namespace std;

/**
 *  lcs(m,n) = 
 *  if x[m] == y[n] lcs[m-1,n-1]+1
 *  max(lcs[m-1,n],lcs[m,n-1])
 *
 */

string x, y;

const int q = 150;

int c[q][q];

int lcs(int m, int n)
{
	if (m == -1 || n== -1) return 0;
	if (x[m] == y[n]) return lcs(m-1,n-1) + 1;
	int & cc = c[m][n];
	if (cc != -1) return cc;
	int xx = lcs(m-1,n);
	int yy = lcs(m,n-1);
	cc = xx > yy ? xx : yy;
	return cc;
}

int main()
{
	int n = 0;
	x.resize(q);
	y.resize(q);
	memset(c, -1, sizeof(c));
	cin >> n; 
	for (int i=0;i<n;i++)
	{
		cin >> x;
		cin >> y;
		cout << lcs(x.size()-1, y.size()-1) << endl;
		x.clear();
		y.clear();
	}
}

C++: #include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};


int main(int argc, char const *argv[]) {
	int N;
	cin >> N;
	for (int i = 0; i < N; ++i) {
		string s1;
		string s2;
		cin >> s1 >> s2;
		int dp[1000][1000] = {{0}};
		for (int i = 0; i < s1.size(); ++i) {
			if (s1[i] == s2[0]) {
				dp[i][0] = 1;
			}
		}
		for (int i = 0; i < s2.size(); ++i) {
			if (s1[0] == s2[i]) {
				dp[0][i] = 1;
			}
		}
		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] = std::max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		cout << dp[s1.size() - 1][s2.size() - 1] << endl;
	}	

	return 0;
}

C++: #include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int c[1005][1005];

int lcs( string X, string Y){

    int m, n, i, j;

    m = X.size();
    n = Y.size();

    X = ' ' + X;
    Y = ' ' + Y;

    int Lmax = 0;

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

        c[i][0] = 0;

    }

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

        c[0][i] = 0;

    }

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

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

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

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

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

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

            } else {

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

            }

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

        }

    }

    return Lmax;

}

int main(){

    int n;
    string X, Y;

    cin >> n;

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

        cin >> X >> Y;

        cout << lcs( X, Y) << endl;

    }

    return 0;

}

C++: #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int main(){
  int n;
  char x[1001],y[1001];
  int dp[1002][1002];
  
  //initialize
  for(int i=0;i<1002;i++){
    for(int j=0;j<1002;j++){
      dp[i][j]=0; 
    }
  }

  //load n;
  cin >>n;
  for(int i=0;i<n;i++){
    //load string
    scanf("%s",x);
    scanf("%s",y);
    //dp
    for(int j=0;j<strlen(x);j++){
      for(int k=0;k<strlen(y);k++){
	if(x[j]==y[k]){
	  dp[j+1][k+1]=dp[j][k]+1;
	}

	else{
	  if(dp[j][k+1]>dp[j+1][k]){
	    dp[j+1][k+1]=dp[j][k+1];
	  }

	  else{
	    dp[j+1][k+1]=dp[j+1][k];
	  }
	}
      }
    }

    //print
    cout <<dp[strlen(x)][strlen(y)]<<endl;
  }



  return 0;
}

C++: #include <iostream>

using namespace std;

int max_length(string x, string y)
{
    int n = x.size();
    int m = y.size();
    int dp[n+1][m+1];
    for(int i = 0; i <= m; ++i)
    {
        dp[0][i] = 0;
    }
    for(int i = 1; i <= n; ++i)
    {
        dp[i][0] = 0;
        for(int j = 1; j <= m; ++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]);
            }
        }
    }
    return dp[n][m];
}

int main()
{
    string str1;
    string str2;
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> str1 >> str2;
        cout << max_length(str1, str2) << endl;
    }
}

C++: #include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int lcs(string x, string y){
    int n = x.size();
    int m = y.size();
    int dp[n+1][m+1];
    for(int i = 0;i<n+1;i++)dp[i][0] = 0;
    for(int j = 0;j<m+1;j++)dp[0][j] = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(x[i]==y[j]){
                dp[i+1][j+1]=dp[i][j]+1;
            }else{
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
            }
        }
    }
    return dp[n][m];
}

int main(){
    int n;cin>>n;
    // string s1,s2;
    for(int i=0;i<n;i++){
        string s1,s2;
        cin>>s1>>s2;
        cout<<lcs(s1,s2)<<endl;
    }
    return 0;
}

C++: #include <iostream>
#include <vector>
#include <string>

int main(){
	int q;
	std::string a, b;
	std::vector< std::vector< int > > dp;
	
	dp.resize(1001);
	for(int i=0;i<=1000;++i){
		dp[i].resize(1001);
	}
	
	std::cin >> q;
	
	for(int i=0;i<q;++i){
		std::cin >> a >> b;
		
		for(int x=1;x<=a.length();++x){
			for(int y=1;y<=b.length();++y){
				if(a[x-1] == b[y-1]){
					dp[x][y] = std::max(std::max(dp[x - 1][y - 1] + 1, dp[x][y - 1]), dp[x - 1][y]);
				}else{
					dp[x][y] = std::max(std::max(dp[x - 1][y - 1], dp[x][y - 1]), dp[x - 1][y]);
				}
			}
		}
		std::cout << dp[a.length()][b.length()] << std::endl;
	}
	
	return 0;
}

C++: #include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const long long INF = 1e9;
const long long MOD = 1e9+7;
using Graph = vector<vector<ll>>;
template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll q; cin >> q;
    rep(Q, q){
        string s, t; cin >> s >> t;
        ll s_size = s.size(), t_size = t.size();

        vector<vector<ll>> dp(s_size+1, vector<ll>(t_size+1));

        for(ll i = 0; i < s_size; i++){
            for(ll j = 0; j < t_size; j++){
                if(s[i] == t[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                }else{
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }

        cout << dp[s_size][t_size] << endl;

    }

}