Go: package main

import (
	"fmt"
	"os"
	"strconv"
	"bufio"
	"strings"
	"sort"
)

// define
var (
	sc = bufio.NewScanner(os.Stdin)
)

func bordersInt(in_map [][]int, invalid int) [][]int{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]int, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]int, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func bordersString(in_map [][]string, invalid string) [][]string{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]string, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]string, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func scanIntLine(len int) []int{
	arr := make([]int, len)
	for i:=0; i<len; i++{
		sc.Scan()
		tmp, err := strconv.Atoi(sc.Text())
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func scanStringLine(len int) []string{
	arr := make([]string, len)
	for i:=0; i<len; i++{
		sc.Scan()
		arr[i] = sc.Text()
	}
	return arr
}

func scanIntSplit(len int) []int{
	arr := make([]int, len)
	sc.Scan()
	for i, v := range strings.Split(sc.Text(), " "){
		tmp, err := strconv.Atoi(v)
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func maxInt(args... int) int{
	sort.Ints(args)
	return args[len(args)-1]
}

func f() {
	var S, T string
	fmt.Scan(&S)
	fmt.Scan(&T)
	lenS, lenT := len(S), len(T)
	dp := make([][]int, lenS+1)
	for i:=0; i<lenS+1; i++ {
		dp[i] = make([]int, lenT+1)
	}
	for i:=1; i<lenS+1; i++ {
		for j:=1; j<lenT+1; j++ {
			if S[i-1] == T[j-1] {
				dp[i][j] = maxInt(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
		}
	}
	fmt.Println(dp[lenS][lenT])
}

func main(){
	var n int 
	fmt.Scan(&n)
	for i:=0; i<n; i++ {
		f()
	}
}

C++: #include <iostream>
#include <string>
#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();

    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;
    }
    int maxl = -100;
    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() {
    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<bits/stdc++.h>
using namespace std;

int DP[1010][1010];

int main(){
	int n;	cin>>n;
	for(int qi=0; qi<n; qi++){
		string s,t;		cin>>s>>t;
		int S=s.length(), T=t.length();
		s=" "+s;	t=" "+t;

		for(int i=0; i<=max(S,T); i++){
			DP[0][i]=DP[i][0]=0;
		}

		for(int i=1; i<=S; i++){
			for(int j=1; j<=T; 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[S][T]<<endl;
	}

	return 0;
}

C++: #include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<list>
#include <array>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define INF I64_MAX
#define MOD 1000000007
#define MEM_SIZE = 1e5+5;

template<typename T> void DEBUG(T e){std::cout << e << std::endl;}
template<class T> void DEBUG(string str, T e){std::cout <<str << ">>" << e << std::endl;}
template<typename T> void DEBUG(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ DEBUG(v); } }
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}



//BELOW
struct mint {
  int x; // typedef long long int;
  mint(int x=0):x((x%MOD+MOD)%MOD){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(int t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime MOD
  mint inv() const {
    return pow(MOD-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
 
 
 
const int MAX = 510000;
 
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}
 
// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[n - k] % MOD) % MOD;
}

//-----CODE------//


void solve(void)
{

  int Q;
  cin>>Q;
  for (int q = 0; q < Q; q++)
  {
    string A,B;
    cin>>A>>B;
    vector<vector<int> > DP(A.size()+1,vector<int>(B.size()+1,0));

    for (int i = 0; i < A.size(); i++)
    {
      for (int j = 0; j < B.size(); j++)
      {
        if(A[i] == B[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[A.size()][B.size()]<<endl;
  }
  
  return; 
}


int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  std::cout << std::fixed;
  std::cout << std::setprecision(9);
  solve();

 
  return 0;
}

C++: #include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <string>
#include <functional>
#include <numeric>
#include <ctype.h>
#include <cstdlib>
#include <string.h>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <utility>
#define rep(i, n) for(int i = 0; i < n; i++);

using namespace std;

const int INF = 1000000007;
const double PI = acos(-1.0);
typedef long long llong;

const int N = 10000;

int search(string X, string Y)
{
	int c[1000 + 1][1000 + 1];
	int m = X.size();
	int n = Y.size();
	int maxl = 0;
	X = " " + X;
	Y = " " + Y;

	for (int i = 1; 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 input1, input2;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> input1 >> input2;
		cout << search(input1, input2) << endl;
	}

	return 0;
	

}