Go: package main

import (
	"bufio"
	"os"
	"io"
	"strconv"
	"math"
	"fmt"
)

var (
	nstr   func() string
	stdout *bufio.Writer
)

func init() {
	nstr = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

func main() {
	defer stdout.Flush()

	n := nint()
	xList := make([]string, n)
	yList := make([]string, n)

	for i:=0;i<n ;i++  {
		xList[i] = nstr()
		yList[i] = nstr()
	}

	for i := 0; i<n	; i++  {
		fmt.Println(lcs(xList[i], yList[i]))
	}

}

func lcs(x string, y string) int{
	var m = len(x)
	var n = len(y)

	c := make([][]int, m+1)
	for i:= range c{
		c[i] = make([]int, n+1)
	}
	for i:=	1;i<=m ;i++  {
		for j:=1;j<=n ;j++  {
			if x[i-1] == y[j-1]{
				c[i][j] = c[i-1][j-1] + 1
			}else{
				c[i][j] = int(math.Max(float64(c[i-1][j]), float64(c[i][j-1])))
			}


		}
	}
	return c[m][n]

}


func newReadString(ior io.Reader) func() string {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	return func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
}

func nint64() int64 {
	i, err := strconv.ParseInt(nstr(), 0, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func nint() int {
	return int(nint64())
}

func getIntSlice(n int) []int {
	b := make([]int, n)
	for i := 0; i < n; i++ {
		b[i] = nint()
	}
	return b
}

func getStringSlice(n int) []string {
	b := make([]string, n)
	for i := 0; i < n; i++ {
		b[i] = nstr()
	}
	return b
}

func gcd(x, y int) int {
	if y == 0 {
		return x
	}
	return gcd(y, x%y)
}

func lcm(x, y int) int {
	return x * y / gcd(x, y)
}

func contains(s []int, e int) bool {
	for _, a := range s {
		if a == e {
			return true
		}
	}
	return false
}

func bin(i int, prefix bool) string {
	i64 := int64(i)

	if prefix {
		return "0b" + strconv.FormatInt(i64, 2)
	} else {
		return strconv.FormatInt(i64, 2)
	}
}

func strReverse(s string) string {
	runes := []rune(s)
	for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
		runes[i], runes[j] = runes[j], runes[i]
	}

	return string(runes)
}

C++: #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]==t[j]){
                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(c[i][j],maxlen);
        }
    }
    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;
}

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

const int s=1001;

using namespace std;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int q;
	static unsigned int dp[s][s] = {0};
	
	dp[0][0] = 0; dp[0][1] = 0; dp[1][0] = 0;

	cin >> q;
	for(int k=0; k < q; k++){
		string X,Y;
		cin >> X >> Y;
		int i,j;
		for(i=0;i<X.size();i++){
			for(j=0;j<Y.size();j++){
				if(X[i] == Y[j]) dp[i+1][j+1] = dp[i][j] + 1;
				else dp[i+1][j+1] = max(dp[i][j+1],dp[i+1][j]);
			}
		}
		cout << dp[i][j] << "\n";
	}
	return 0;
}

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;
}