Go: package main

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

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

/*********************************************************************
長さmの列X_(m)と長さnの列Y_(n)の最長共通部分列LCSは、
	(1)X[m] == Y[n]ならば、X_(m-1)とY_(n-1)のLCSにX[m]を繋げたもの
	(2)X[m] != Y[n]ならば、X_(m-1)とY_(n)のLCSもしくはX_(m)とY_(n-1)のLCS
	のいずれかのうち長い方

c[m+1][n+1]：c[i][j]にX_(i)とY_(j)のLCSの長さを格納する二次元配列
*********************************************************************/

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	n, _ := strconv.Atoi(scanner.Text())
	for i := 0; i < n; i++ {
		scanner.Scan()
		s1 := scanner.Text()
		scanner.Scan()
		s2 := scanner.Text()
		s1, s2 = s1 + " ", s2 + " "
		c := make([][]int, len(s1))
		for i := range c {
			c[i] = make([]int, len(s2))
		}

		LCS := 0

		for i := 1; i < len(s1); i++ {
			for j := 1; j < len(s2); j++ {
				if s1[i] == s2[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])
			}
		}
		fmt.Println(LCS)
	}
}

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

using namespace std;

int main() {
    int a;
    string s,t;
    cin >> a;

    for(int ai = 0; ai < a; ai++) {
        cin >> s >> t;
        int n = s.length(), m = t.length();

        int dp[n+1][m+1];
        fill_n(dp[0], (n+1)*(m+1), 0);
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; 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[n][m] << endl;
    }
}

C++: #include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;

int larger(int x, int y){
	if(x > y){
		return x;
	}
	return y;
}

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

C++: #include <stdio.h>
#include <string.h>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define repi(i, n) for(int i = 1; i < n; ++i)

int max(int a, int b) {
  return a > b ? a : b;
}

int main(void) {
  int n;
  scanf("%d", &n);
  rep(i, n) {
    char x[1500], y[1500], h, w;
    scanf("%s", x);
    scanf("%s", y);
    h = strlen(x), w = strlen(y);
    int dp[h][w], len[w], maxs = 0;
    rep(j, h) rep(k, w) dp[j][k] = 0;
    rep(j, w) if(x[0] == y[j]) dp[0][j] = 1;
    len[0] = 0;
    repi(j, w) len[j] = max(dp[0][j - 1], len[j - 1]);
    repi(j, h) {
      rep(k, w) if(x[j] == y[k]) {
        dp[j][k] = len[k] + 1;
        if(maxs < dp[j][k]) maxs = dp[j][k];
      }
      repi(k, w) len[k] = max(dp[j][k - 1], max(len[k], len[k - 1]));
      /*rep(k, w) printf("%d ", len[k]);
      printf("\n");*/
    }
    /*printf("\n");
    rep(j, h) {
      rep(k, w) printf("%d ", dp[j][k]);
      printf("\n");
    }*/
    printf("%d\n", maxs);
  }
  return 0;
}

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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ull unsigned long long
#define ld long double

template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;
template <class T>
using VVV = V<V<V<T>>>;

#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) rep2(i, 0, n)
#define rep1(i, n) rep1(i, 1, n + 1)

// #define repr(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
// #define rep1r(i, n) for (int i = ((int)(n)); i >= 1; i--)

#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()  //

#define SORT(v, n) sort(v, v + n);
#define VSORT(v) sort(v.begin(), v.end());
#define RSORT(x) sort(rall(x));

#define INF (1e9)
#define PI (acos(-1))
#define EPS (1e-7)

// 総数を1000000007（素数）で割った余り
const long long mod = 1e9 + 7;

const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int dy[] = {1, 0, -1, 0, -1, 1, 1, -1};

ull gcd(ull a, ull b) { return b ? gcd(b, a % b) : a; }
ull lcm(ull a, ull b) { return a / gcd(a, b) * b; }

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(15);
    //    cout << std::setfill('0') << std::setw(2);

    int Q;
    cin >> Q;
    rep(q, Q) {
        string S, T;
        cin >> S >> T;
        int s = S.size(), t = T.size();
        VV<int> dp(s + 1, V<int>(t + 1, 0));
        dp[0][0] = 0;
        rep(i, s) dp[i][0] = 0;
        rep(i, t) dp[0][i] = 0;

        rep2(i, 1, s + 1) rep2(j, 1, t + 1) {
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            if (S[i - 1] == T[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        cout << dp[s][t] << endl;
    }

    return 0;
}

C++: #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#define MAX_L (1010)
using namespace std;

int q;
int dp[2][MAX_L];

int main()
{
    scanf("%d", &q);


    for ( int i = 0; i < q; i++ ) {
	string a, b;
	char str[MAX_L];
	scanf("%s", str);
	a = str;
	scanf("%s", str);
	b = str;	
	memset(dp, 0, 2 * MAX_L * sizeof(int));
	
	for ( int j = 1; j <= a.length(); j++ ) {
	    for ( int k = 1; k <= b.length(); k++ ) {
		if ( a[j-1] == b[k-1] ) {
		    dp[j%2][k] = dp[(j-1)%2][k-1] + 1;
		}
		else {
		    dp[j%2][k] = max(dp[(j-1)%2][k], dp[j%2][k-1]);
		}
	    }
	}
	printf("%d\n", dp[(a.length())%2][b.length()]);
    }

    return 0;
}

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

#define MOD 1000000007
#define INF (1<<30)
#define INFL (1<<62)
#define pe(str) return cout<<(str)<<endl,0
#define px(str) cout<<(str)<<endl,exit(0)
#define accu(ac,v) cout<<setprecision(ac)<<v<<endl
#define bpc(a) __builtin_popcount(a)
#define pr(str) cout<<(str)<<endl
#define prpr(str) cout<<str<<endl
#define db(str) cerr<<"debug:"<<(str)<<endl
#define dbdb(str) cerr<<"debugs:"<<str<<endl
#define re(i,n) for(int i=0;i<(n);i++)
#define rre(i,n) for(int i=(n);i>=0;i--)
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b);i>=(a);i--)
#define bw(a,b,c) (((a)<=(b))&&((b)<=(c)))
#define hello cout<<"hello"<<endl
#define spre(a) setprecision(a)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define s3(C,T,F) ((C)?(T):(F))
#define max3(a,b,c) max((a),max((b),(c)))
#define min3(a,b,c) min((a),min((b),(c)))
#define max4(a,b,c,d) max((a),max((b),max((c),(d))))
#define min4(a,b,c,d) min((a),min((b),min((c),(d))))
#define enl cout<<endl
#define declare(t,n) t n;cin>>n

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef complex<int> point;

template<class InputIterator>
void dump(InputIterator first,InputIterator last,char delim=' '){
	for(InputIterator it=first;it!=last;it++){
		if(it!=first)cout<<delim;
		cout<<*it;
	}
}

ull p(ull x,ull y){
	if(y==0) return 1;
	ull A=p(x,y/2)%MOD;
	return (y&1?((A*A)%MOD*x)%MOD: (A*A)%MOD);
	// return (y&1?((A*A)*x):(A*A));
}

template<class T>
void swp(T &a,T &b){
	T t=a; a=b; b=t;
}

int main(void){
	int dp[100][100];
	string a,b;
	int n;
	cin>>n;

	while (n--) {
		cin>>a>>b;
		re(i,a.size()) re(j,b.size()) dp[i][j]=0;
		rep(i,1,a.size()+1){
			rep(j,1,b.size()+1){
				dp[i][j]=max(dp[i-1][j-1]+(a[i-1]==b[j-1]),dp[i-1][j]);
				dp[i][j]=max(dp[i][j],dp[i][j-1]);
			}
		}
		cout<<dp[a.size()][b.size()]<<endl;
	}
	return 0;
}