Go: package main

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

//Util
func nextStr() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func maxInt(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

func minInt(a, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func absInt(a int) int {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func absFloat64(a float64) float64 {
	if a >= 0 {
		return a
	} else {
		return -a
	}
}

func minFloat64(a, b float64) float64 {
	if a > b {
		return b
	} else {
		return a
	}
}

func str2Int(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

//Main
var sc = bufio.NewScanner(os.Stdin)
var q int
var X, Y string

func lcs(X, Y string) int {
	lenX := len(X)
	lenY := len(Y)
	dp := make([][]int, lenX+1)
	for i := 0; i < lenX+1; i++ {
		dp[i] = make([]int, lenY+1)
	}

	res := 0
	for i := 1; i < lenX+1; i++ {
		for j := 1; j < lenY+1; j++ {
			if X[i-1] == Y[j-1] {
				dp[i][j] = dp[i-1][j-1] + 1
			} else {
				dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
			}
			//fmt.Println(dp)
			res = maxInt(res, dp[i][j])
		}

	}
	return res
}

func main() {
	sc.Split(bufio.ScanWords)
	q = nextInt()

	for i := 0; i < q; i++ {
		X = nextStr()
		Y = nextStr()

		fmt.Println(lcs(X, Y))
	}
}

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

//#define int long long
//struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;
//const int MOD = 1e9 + 7;
using intpair = pair<int, int>;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((int)((a) + (b) - 1)/(int)(b))

int dp[1001][1001];

inline bool chmax(int &a, int b){
    if(a < b) a = b;
    return a < b;
}

signed main() {
    int Q; cin >> Q;
    while(Q--){
        string s, t;
        cin >> s >> t;
        int n = (int)s.length();
        int m = (int)t.length();
        
        rep(i,n+1)rep(j,m+1) dp[i][j] = 0;
        
        reps(i,1,n)reps(j,1,m){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            if(s[i-1] == t[j-1]){
                chmax(dp[i][j], dp[i-1][j-1]+1);
            }
        }
        
        cout << dp[n][m] << endl;
    }
}

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

using namespace std;

static const int N = 1000;

static int lcs(string& s1, string& s2) {
	int table[N + 1][N + 1];
	int m = s1.size();
	int n = s2.size();
	int max_len = 0;
	s1 = ' ' + s1;
	s2 = ' ' + s2;

	for (int i = 0; i <= m; i++) table[i][0] = 0;
	for (int j = 0; j <= m; j++) table[0][j] = 0;
	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (s1[i] == s2[j]) {
				table[i][j] = table[i - 1][j - 1] + 1;
			}
			else {
				table[i][j] = max(table[i - 1][j], table[i][j - 1]);
			}

			max_len = max(table[i][j], max_len);
		}
	}

	return max_len;
}

int main() {
	int n;
	cin >> n;

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

	return 0;
}

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

int Longest(string x, string y) {
  int L[1001][1001];
  int maxl = -1;
  int xlen = x.size();
  int ylen = y.size();

  x = ' ' + x;
  y = ' ' + y;

  for (int i = 1; i <= xlen; i++) L[i][0] = 0;
  for (int j = 1; j <= ylen; j++) L[0][j] = 0;

  for (int i = 1; i <= xlen; i++) {
    for (int j = 1; j <= ylen; j++) {
      if (x[i] == y[j])
        L[i][j] = L[i-1][j-1] + 1;
      else
        L[i][j] = max(L[i][j-1], L[i-1][j]);

      maxl = max(maxl, L[i][j]);
    }
  }

  return maxl;
}

int main() {
  string X, Y;
  int n;
  int result;

  cin >> n;

  for (int i = 0; i < n; i++) {
    cin >> X;
    cin >> Y;
    cout << Longest(X, Y) << endl;
  }

  


  return 0;
}

C++: #include <iostream>
#include <algorithm>
#include<string.h>
using namespace std;
int LCS(char *x,char *y);
char x[1001], y[1001];
int lcs[1001][1001];
int main()
{
	int q,i,j;

	cin >> q;
	for (i = 0; i < q; i++) {
		cin >> x;
		cin >> y;
		cout << LCS(x, y) << endl;
	}
}

int LCS(char *x, char *y)
{
	int i, j;
	int len_x, len_y;
	len_x = strlen(x);
	len_y = strlen(y);
	
	for (i = 1; i <+ len_x; i++) {
		for (j = 1; j <+ len_y; j++) {
			if (x[i-1] == y[j-1]) {
				lcs[i][j] = lcs[i - 1][j - 1] + 1;
				//printf("lcs[%d][%d]=%d\n", i, j, lcs[i - 1][j - 1] + 1);
			}
			if (x[i] != y[j]) {
				lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1]);
				//printf("lcs[%d][%d]=%d\n", i, j, max(lcs[i - 1][j], lcs[i][j - 1]));
			}
		}
	//cout << endl;

	}
	for (i = 0; i < len_x; i++) {
		for (j = 0; j < len_y; j++) {
			//printf("%d ", lcs[i][j]);
		}
		//cout << endl;
	}
	//cout << "len_x=" << len_x << endl << "len_y=" << len_y << endl;
			
	return lcs[i-1][j-1];
}

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

using namespace std;

static const int N = 1000;
static int c[N + 1][N + 1] = {};

static int lcs(string& X, string& Y) {
  const size_t m(X.size());
  const size_t n(Y.size());
  X = ' ' + X;
  Y = ' ' + Y;

  int lcs = 0;
  
  for (size_t i = 1; i <= m; i++) {
    for (size_t 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]);
      }
      lcs = max(lcs, c[i][j]);
    }
  }
  return lcs;
}

int main() {
  int n;
  cin >> n;

  string X, Y;
  for (int i = 0; i < n; i++) {
    cin >> X;
    cin >> Y;
    cout << lcs(X, Y) << endl;
  }
 
  return 0;
}

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

int lcs(string X, string Y) {
  int dp[1000 + 1][1000 + 1];
  int max = 0;
  int m = X.size();
  int n = Y.size();
  X = ' ' + X;
  Y = ' ' + Y;
  for(int i = 1; i <= m; i++)
    dp[i][0] = 0;
  for(int i = 1; i <= n; i++)
    dp[0][i] = 0;
  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 if(dp[i - 1][j] >= dp[i][j - 1])
	dp[i][j] = dp[i - 1][j];
      
      else
	dp[i][j] = dp[i][j - 1];
      if(max < dp[i][j])
	max = dp[i][j];
    }
  }
  return max;
}

int main() {
  int N = 0;
  cin >> N;
  string X, Y;
  for(int i = 0; i < N; i++) {
    cin >> X >> Y;
    cout << (int)lcs(X, Y) << endl;
  }  return 0;
}

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

using namespace std;

int lcs(string X,string Y){
  //staticにしないと実行時にスタックオーバーフローになる
  static 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);
  }
  return 0;
}

C++: #include <iostream>

using namespace std;

int lcs(string X, string Y) {
  int memo[1010][1010];
  // 初期化
  for (int i = 0; i < X.size(); i++) {
    memo[i][0] = 0;
  }
  for (int i = 0; i < Y.size(); i++) {
    memo[0][i] = 0;
  }
  int maxl = 0;
  for (int i = 0; i < X.size(); i++) {
    for (int j = 0; j < Y.size(); j++) {
      if (X[i] == Y[j]) {
        memo[i][j] = memo[i-1][j-1] + 1;
      } else {
        memo[i][j] = max(memo[i-1][j], memo[i][j-1]);
      }
      maxl = max(maxl, memo[i][j]);
    }
  }
  return maxl;
}

int main() {
  int q;
  cin >> q;
  for (int i = 0; i < q; i++) {
    string X, Y;
    cin >> X >> Y;
    cout << lcs(X, Y) << endl;
  }
}