Go: package main

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

type Position struct {
	X int
	Y int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	n, err := nextInt(sc)
	if err != nil {
		panic(err)
	}
	for i := 0; i < n; i++ {
		strX := nextText(sc)
		strY := nextText(sc)
		fmt.Println(calcLcs(strX, strY))
	}
}

func calcLcs(strX, strY string) int {
	return lcs(strX, strY, Position{0, 0}, make(map[Position]int))
}

func lcs(strX string, strY string, position Position, memo map[Position]int) int {
	if position.X >= len(strX) || position.Y >= len(strY) {
		return 0
	}
	if v, ok := memo[position]; ok {
		return v
	}
	if strX[position.X] == strY[position.Y] {
		result := lcs(strX, strY, Position{position.X + 1, position.Y + 1}, memo)
		memo[position] = result + 1
		return memo[position]
	} else {
		result1 := lcs(strX, strY, Position{position.X + 1, position.Y}, memo)
		result2 := lcs(strX, strY, Position{position.X, position.Y + 1}, memo)
		var result int
		if result1 > result2 {
			result = result1
		} else {
			result = result2
		}
		memo[position] = result
		return result
	}
}

func nextInt(sc *bufio.Scanner) (int, error) {
	sc.Scan()
	return strconv.Atoi(sc.Text())
}

func nextText(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

C++: #include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i < (n+1); ++i)
using namespace std;
using ll = long long;
// const int INF = +100100100;
// typedef pair<int,int> P;

// int dp(int i, int j, string x, string y, char D[MAX][MAX]){
//     if(x[i-1]==y[j-1])return D[i-1][j-1]+1;
//     else{
//         return max(D[i-1][j],D[i][j-1]);
//     }
// }

int lcs(string x, string y){
    int D[x.size()+1][y.size()+1];
    rep(i,x.size()+1)D[i][0]=0;
    rep(i,y.size()+1)D[0][i]=0;
    rrep(i,x.length()){
        rrep(j,y.length()){
            if(x[i-1]==y[j-1])D[i][j]= D[i-1][j-1]+1;
            else{
                D[i][j]= max(D[i-1][j],D[i][j-1]);
            }
        }
    }
    int ans = D[x.length()][y.length()];
    return ans;
}

int main(){
    int n;cin>>n;
    rep(i,n){
        string x,y;
        cin >> x >> y;
        printf("%d\n",lcs(x,y));
    }
    return 0;
}

C++: #include<iostream>
#include<string>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
map <char,vector<int>> alx,aly;//x,y
int memo[1010][1010];
string x,y,q;
int lcs(int xn,int yn){//yn文字目以降でX[xn]と同じやつを探す
    if(memo[xn][yn]!=-1)return memo[xn][yn];
    int ans=0;
	/*
    for(int i=xn; i<x.size();i++){
        for(int j=yn; j<y.size(); j++){
            if(alx[x[i]]==aly[y[j]]){
                ans=max(ans,lcs(i+1,j+1)+1);
            }
        }
    }
	*/
	for(int i=xn; i<x.size();i++){
        for(int j=0; j<aly[x[i]].size(); j++){
			if(aly[x[i]][j] < yn) continue;
			ans=max(ans,lcs(i+1,aly[x[i]][j]+1)+1);
		}
    }
    return memo[xn][yn]=ans;
}
 
 
int main(){
    int q;
    cin >> q;
    for(int ds=0; ds<q; ds++){
 
        cin >> x >> y;
        for(int i=0; i<=x.size(); i++){
            for(int j=0; j<=y.size(); j++){
				memo[i][j]=-1;
			}
        }

		for(int i=0; i<x.size(); i++) alx[x[i]].push_back(i);
		for(int i=0; i<y.size(); i++) aly[y[i]].push_back(i);
		

        //memset(memo, -1, sizeof(memo));
         
        cout << lcs(0,0) << endl;
 
    }
    return 0;
}

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

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

string str1, str2;
int dp[1001][1001];

void solve()
{
  REP(i, str1.size())
    if(str1[i] == str2[str2.size() - 1])
      dp[i][str2.size() - 1] = 1;
    else
      dp[i][str2.size() - 1] = 0;
  for(int i = str2.size() - 2; i >= 0; i--)
    if(str1[str1.size() - 1] == str2[i])
      dp[str1.size() - 1][i] = 1;
    else
      dp[str1.size() - 1][i] = dp[str1.size() - 1][i + 1];
  for(int i = str1.size() - 2; i >= 0; i--){
    for(int j = str2.size() - 2; j >= 0; j--){
      if(str1[i] == str2[j])
	dp[i][j] = dp[i + 1][j + 1] + 1;
      else
	dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
    }
  }
}
  
int main()
{
  int q;
  cin >> q;
  cin.ignore();
  REP(i, q){
    getline(cin, str1);
    getline(cin, str2);
    if(str1.size() < str2.size())
      swap(str1, str2);
    fill(&dp[0][0], &dp[1001][0], -1);
    solve();
    cout << dp[0][0] << endl;
  }
}

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

#define MAX_N 1000
#define MAX_M 1000

void solve();

string s, t;
int dp[MAX_N + 1][MAX_M + 1];

void solve(){
	for(int i = 0; i < s.length(); i++){
		for(int j = 0; j < t.length(); j++){
			if(s[i] == t[j]){
				dp[i + 1][j + 1];
					dp[i + 1][j + 1] = dp[i][j] + 1;
				} else {
					dp[i + 1][j + 1] = max(dp[i][j], dp[i + 1][j]);
				}
			}
		}
		cout << dp[s.length()][t.length()] << endl;
}

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> s >> t;
		solve();
	}
	return 0;
}

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();
  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 s1, s2;
  int q;
  cin >> q;

  for ( int i = 0; i < q; i++ ) {
    cin >> s1 >> s2;
    cout << lcs(s1, s2) << endl;
  }

  return 0;
}

C++: #include<iostream>
#include<string>
#include<string.h>

using namespace std;

int lcs(char x[],char y[]);

int main(){
	char x[1000],y[1000];
	int n,*memo; cin>>n;
	memo = new int[n];
	for(int i=0;i<n;i++){
		cin>>x>>y;
		memo[i] = lcs(x,y);
	}
	for(int i=0;i<n;i++)
		cout<<memo[i]<<endl;

	delete [] memo;
}

int lcs(char x[],char y[]){
	int m = strlen(x), n = strlen(y);
	int **c,a;
	c = new int*[m+1]; for(int i=0;i<=m;i++) c[i] = new int[n+1];
	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-1]==y[j-1]){
				c[i][j] = c[i-1][j-1]+1;
				if(i==m&&j==n){
					a = c[i][j];
					//cout<<c[i][j]<<endl;
				}
			}else{
				if(c[i-1][j]>=c[i][j-1]){
					c[i][j] = c[i-1][j];
					if(i==m&&j==n){
						a = c[i][j];
						//cout<<c[i][j]<<endl;
					}
				}else{
					c[i][j] = c[i][j-1];
					if(i==m&&j==n){
						a = c[i][j];
						//cout<<c[i][j]<<endl;
					}
				}
			}
		}
	}
	for(int i=0;i<=strlen(x);i++) delete [] c[i]; delete [] c;
	return a;
}

C++: #include<bits/stdc++.h>
using namespace std;

int lcs(string X,string Y){
  int c[1001][1001];
  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(){
  int q;cin>>q;
  while(q--){
    string a,b;cin>>a>>b;
    cout<<lcs(a,b)<<endl;
  }
  return 0;
}