Go: package main

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

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 {
	lenX, lenY := len(strX), len(strY)
	memo := make([][]int, lenX+1)
	for i := 0; i < lenX+1; i++ {
		memo[i] = make([]int, lenY+1)
	}

	lcs := 0
	for i := 1; i < lenX+1; i++ {
		for j := 1; j < lenY+1; j++ {
			if strX[i-1] == strY[j-1] {
				memo[i][j] = memo[i-1][j-1] + 1
			} else {
				if memo[i-1][j] > memo[i][j-1] {
					memo[i][j] = memo[i-1][j]
				} else {
					memo[i][j] = memo[i][j-1]
				}
			}
			if memo[i][j] > lcs {
				lcs = memo[i][j]
			}
		}
	}
	return lcs
}

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 <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <functional>

using namespace std;
using ll = long long int;
#define rep(i,n) for(int i = 0; i < n; i++)
#define FOR(i, a, b)  for(int i = (a); i < (b) ; i++)
#define pb push_back
#define SORT(v,n) sort(v, v+n)
#define ALL(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << ": " << x << '\n'
#define elif else if
#define itn ll
#define int ll
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
///                →,↑,←,↓,↗,↖,↙,↘
int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };


static const int N = 1000;

int lcs(string X, string Y) {
	int c[N + 1][N + 1];
	int maxl = 0;
	int i, j;
	int m = X.size();
	int n = Y.size();
	X = ' ' + X;
	Y = ' ' + Y;
	FOR(i, 1, m+1) {
		c[i][0] = 0;
	}
	FOR(i, 1, n+1) {
		c[0][i] = 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(c[i][j], maxl);
		}
	}
	return maxl;
}

signed main() {
	ios::sync_with_stdio(false);
	int n;
	string s1, s2;
	cin >> n;
	int i;
	rep(i, n) {
		cin >> s1 >> s2;
		cout << lcs(s1, s2) << "\n";
	}
	return 0;
}

C++: #include <iostream>
#include <vector>
#include <numeric>

using namespace std;

int main() {
    int32_t q;
    cin >> q;

    while (q--) {
        string X, Y;
        cin >> X >> Y;

        vector<int32_t> lcs((X.size()+1)*(Y.size()+1));
        fill(lcs.begin(), lcs.end(), 0);

        for (int32_t i = 1; i <= X.size(); i++) {
            for (int32_t j = 1; j <= Y.size(); j++) {
                lcs[i*(Y.size()+1)+j] = max(lcs[(i-1)*(Y.size()+1)+j], lcs[i*(Y.size()+1)+j-1]);
                if (X[i-1] == Y[j-1]) {
                    lcs[i*(Y.size()+1)+j] = max(lcs[i*(Y.size()+1)+j], lcs[(i-1)*(Y.size()+1)+j-1] + 1);
                }
            }
        }

        cout << lcs.back() << endl;

    }

    return 0;
}

C++: #include <bits/stdc++.h>
#define int long long
#define double long double
#define rep(i, a, n) for(int i = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int i = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int i = (int)(a);(x);++(i))
#define repr(i, a, n) for(int i = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int i = (int)(a);(i) >= (int)(n);--(i))
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), end(x))
#define gcd(x, y) __gcd(x, y)
#define lcm(x, y) ((x)/gcd(x,y)*(y))
#define isin(x, l, r) ((l) <= (x) and (x) < (r))
#define fcout(n) cout << fixed << setprecision(n)
#define rcout(n) cout << right << setw(n)
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define PI (acosl(-1))
#define EPS (1e-10)
#define INF LLONG_MAX
#define INF32 INT32_MAX
#define MOD 1000000007LL
using namespace std;
using VI = vector<int>;
using PII = pair<int, int>;
using TIII = tuple<int, int, int>;
using VPII = vector<PII>;
using VTIII = vector<TIII>;
using Complex = complex<double>;
template<typename T, template<typename> typename C = less> using PQ = priority_queue<T, vector<T>, C<T>>;
template<typename T> inline bool chmax(T& a, const T& b, bool t = false){ if(a<b or (t and a == b)){ a=b; return true; } return false; }
template<typename T> inline bool chmin(T& a, const T& b, bool t = false){ if(a>b or (t and a == b)){ a=b; return true; } return false; }


signed main(){
    int q;
    cin >> q;
    while(q--){
        string X, Y;
        cin >> X >> Y;
        vector<VI> dp(SZ(X)+1, VI(SZ(Y)+1));
        rep(i, 0, SZ(X)) rep(j, 0, SZ(Y)){
            if(X[i] == Y[j]) dp[i+1][j+1] = dp[i][j]+1;
            else chmax(dp[i+1][j+1], max(dp[i+1][j], dp[i][j+1]));
        }
        cout << dp[SZ(X)][SZ(Y)] << endl;
    }

    return 0;
}

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

#define NUM 1000
int dp[NUM + 1][NUM + 1];

void calc(string X, string Y){
    for(int i = 0; i <= X.size(); i++){
        for(int j = 0; j <= Y.size(); j++){
            dp[i][j] = 0;
        }
    }

    for(int j = 1; j <= Y.size(); j++){
        for(int i = 1; i <= X.size(); i++){
            if(X[i - 1] == Y[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }else{
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    printf("%d\n", dp[X.size()][Y.size()]);

}

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

    for(int i = 0; i < q; i++){
        string X;
        string Y;
        cin >> X;
        cin >> Y;
        calc(X, Y);
    }
}

C++: #include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <utility>
using namespace std;
//_____
#define pb push_back
#define fi first
#define se second
#define mkp make_pair
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0; i<(n); ++i)
#define reps(i,f,n) for(int i=(f); i<=(n); ++i)
#define err(...) fprintf(stderr, __VA_ARGS__)
#define show(x) cerr << #x << ':' << x << endl
#define outl(x) cout << (x) << '\n'
#define FAST() cin.tie(0), ios::sync_with_stdio(false)
typedef long long ll;
typedef pair<int,int> pii;
template<class A, class B>inline bool chmax(A &a, B b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, B b){return b<a ? a=b,1 : 0;}
inline bool inside(int y, int x, int H, int W){return(y>=0 && x>=0 && y<H && x<W);}
const int INF = 1 << 29;
const int dx[] = {1, 0, -1, 0,  1, 1, -1, -1};
const int dy[] = {0, 1, 0, -1,  -1, 1, 1, -1};
#define LEN 1000011
#define NIL -1
//_______

int dp[1005][1005];

int slv(string &a, string &b)
{
   const int alen = a.size();
   const int blen = b.size();
   a = ' ' + a;
   b = ' ' + b;
   int ret = 0;
   reps(i, 0, alen)dp[0][i] = 0;
   reps(i, 0, blen)dp[i][0] = 0;

   reps(i, 1, alen){
      reps(j, 1, blen){
         if(a[i] == b[j]){
            dp[i][j] = dp[i-1][j-1] + 1;
         } else {
            dp[i][j] = max(dp[i-1][j] , dp[i][j-1] );
         }
         chmax(ret, dp[i][j]);
      }
   }
   return(ret);
}

signed main()
{
   FAST();
   int N;
   cin >> N;
   rep(i, N){
      string a,b;
      cin >> a >> b;
      outl( slv(a, b) );
   }
}