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 <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<ll> vec;
typedef vector<vec> vec2;
typedef map<ll,ll> MPll;
typedef set<ll> setl;

const ll INF = 1ll << 60;
const ld EPS = 1e-10;
const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};
const ll mods = 1000000007;

//for文
#define FOR(i,a,b) for(ll i = (ll)a;i < (ll)b;i++)
#define FORE(i,a,b) for(ll i = (ll) a;i <= (ll) b;i++ )
#define REP(i,size)  for(ll i =(ll)0;i<size;i++)
#define REPE(i,size)  for(ll i =(ll)0;i<=size;i++)
#define REPR(i,size)  for(ll i =(ll)size;i>=0;i--)
#define FOREACH(it, vec) for (auto it = vec.begin(); it != vec.end(); it++)

//ソート
#define ALL(vec) (vec).begin(),(vec).end()
#define SORT(vec) sort(ALL(vec))
#define SORTA(arr) sort(arr,arr + (sizeof(arr) / sizeof(ll)))
#define INVSORT(vec) sort((vec).rbegin(),(vec).rend())
#define REV(vec) reverse(ALL(vec))
#define REVA(arr) reverse(arr,arr + (sizeof(arr) / sizeof(ll)))
#define INVSORTA(arr) sort(arr,arr + (sizeof(arr) / sizeof(ll))),REVA(arr)

//最大値最小値
#define MAX(vec) *max_element(ALL(vec))
#define UNIQ(vec) SORT(vec);vec.erase(unique(ALL(vec)),vec.end())
#define MIN(vec) *min_element(ALL(vec))

//出力
#define printl(a) cout << a << "\n"
#define print(a) cout << a
#define OUT(a) printf("%lld\n",a)
#define OUTA(array) REP(i,sizeof(array)/sizeof(ll)) printf("%lld\n",array[i])
#define OUTV(vec) REP(i,vec.size()) printf("%lld\n",vec[i])
#define SP printf(" ")

//入力
#define IN(x) scanf("%lld",&x)
#define INV(vec) REP(i,vec.size()) scanf("%lld",&vec[i])
#define INA(array) REP(i,sizeof(array)/sizeof(ll)) scanf("%lld",array + i)
#define INS(x) cin >> x
#define INCH(x) scanf(" %c",&x)

//型
#define P pair
#define vp vector<P>
#define F first
#define Ssum second

//その他
#define PB push_back
#define MP make_pair
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,-1,sizeof(a))
#define INFI(a) memset(a,INF,sizeof(a))
#define MEM(a,b) memset(a,(b),sizeof(a))

//関数
template<class T> inline void amax(T &a,const T &b) { if(a < b) a = b; }
template<class T> inline void amin(T &a, const T &b) { if(a > b) a = b; }
/*
struct structure{
    ll num1,num2,string s;
    bool operator<(const rest &another) const{
        return this->s < another.s;
    }
    structure(ll a,ll b,string s){
        this->num1 = a,this->num2=b,this->s=s;
    }
};a
*/
//特殊
//#define int ll
#define _CRT_SECURE_NO_WARNINGS



/*
template <typename T>
struct UnionFindTree{

    vector<T> par;
    vector<T> num;

    UnionFindTree(T n) : par(n+1),num(n+1,1ll){
        for (int i = 1; i <= n; ++i) {
            par[i] = i;
            num[i] = 1;
        }
    }

    T root(T x){
        if(par[x] == x) return x;
        else  return par[x] = root(par[x]);
    }

    void unite(T x,T y){
        x = root(x);
        y = root(y);
        if(!same(x,y)) {
            if(num[x] < num[y]) swap(x,y);
            par[y] = x;
            num[x] += num[y];
            num[y] = 0;
        }
    }

    T same(T x,T y){
        return root(x) == root(y);
    }

    T maxnodes(){
        return MAX(num);
    }

};
 */


#define DEBUG

#ifdef DEBUG
#define debugl(x) cerr << #x << ":" << x<<"\n"
#define debug(x)  cerr << #x<<":"<<x<<endl;
#define  debugV(V) REP(iiiii,V.size()){cerr << iiiii << ":" << V[iiiii]<<endl;}
#define  debugA(A) REP(iiiiiii,sizeof(A)/sizeof(ll)){cerr << iiiiiii << ":" << V[iiiiiii]<<endl;}
#define  debugVV(V) REP(i123,V[0].size()){cerr << endl;REP(i1234,V.size()){cerr << V[i1234][i123];}}

#else
#define debug(x)
#define debugV(x)
#define debugA(x)
#define debugl(x)
#endif

#define ZERO(a) memset(a,0,sizeof(a))
#define ALL(vec) (vec).begin(),(vec).end()
#define SORT(vec) sort(ALL(vec))



ll binary(ll key,vec &a){
    ll ok = a.size();ll dame = -1;
    while(abs(ok - dame) > 1){
        ll mid = (ok + dame) /2;
        if(a[mid] <= key) ok = mid;
        else dame = mid;
    }

    return ok;
}


ll n;
ll m;
ll k;
ll l;
ll temp;
ll x,y;
ll H,W;
char c;
ll ddy,ddx;

signed main() {
    IN(n);


    FOR(k,0,n) {
        string S;
        string T;
        INS(S);
        INS(T);
        ll s = S.size();
        ll t = T.size();
        l = max(s,t);
        vec2 dp(s+10,vec(t+10,0));
        FOR(i, 0, s)
            FOR(j, 0, t) {
                if (S[i] == T[j]) amax(dp[i + 1][j + 1], dp[i][j] + 1);
                amax(dp[i + 1][j + 1], dp[i + 1][j]);
                amax(dp[i + 1][j + 1], dp[i][j + 1]);
            }

        OUT(dp[s][t]);
    }

}

C++: #include <cstdio>
#include <cmath>
#define MAX 1002
using namespace std;

int Lcc(const char *X, const char *Y) {
    int lcc = 0;
    int dp[MAX][MAX];
    for (int i=0; i<MAX; i++)
        for (int j=0; j<MAX; j++) dp[i][j] = 0;

    int x=1, y=1;
    for (int i=0;;i++) {
        if (X[i] == ',') {x = i;break;}
        for (int j=0;;j++) {
            if (Y[j] == ',') {
                y = j;
                break;
            }
            if (Y[j] == ',') {
                y = j;
                break;
            } else {
                if (X[i] == Y[j]) {
                    dp[i+1][j+1] = fmax(dp[i][j] + 1, dp[i+1][j]);
                } else {
                    dp[i+1][j+1] = fmax(dp[i+1][j], dp[i][j+1]);
                }
            }
        }
    }
    return dp[x-1][y-1];
}

int
main()
{
    int q;
    scanf("%d", &q);
    for (int i=0; i<(q); i++) {
        char X[MAX], Y[MAX];
        for (int i=0; i<MAX; i++) {
            X[i] = ','; Y[i] = ',';
        }
        scanf(" %s", X);scanf(" %s", Y);
        int LCC = Lcc(X, Y);
        printf("%d\n", LCC);
    }
    return 0;
}

C++: #include <stdio.h>

int score[1010][1010];

int max2 (int a, int b){
  if (a >= b) return a;
  else return b;
}

int len_of_str(const char s[]){
  int num = 0;

  while(s[num]) num++;

  return num;
}


int main() {
  char a[1010];
  char b[1010];
  int datanum;
  scanf("%d",&datanum);
  for(int c = 0; c < datanum; c++){

  scanf("%999s",a);
  scanf("%999s",b);
  int num1 = len_of_str(a);
  int num2 = len_of_str(b);


  for(int i = num1; i > 0; i--) a[i] = a[i - 1];
  a[0] = ' ';
  for(int j = num2; j > 0; j--) b[j] = b[j - 1];
  b[0] = ' ';

  for(int i = 0; i <= num1; i++) score[i][0] = 0;
  for(int j = 0; j <= num2; j++) score[0][j] = 0;

  int maximum = 0;

  for(int i = 1; i<= num1; i++){
    for (int j = 1; j <= num2; j++){
      if (a[i] == b[j])score[i][j] = score[i-1][j-1] + 1;
      else max2(score[i][j-1],score[i-1][j]);
      maximum = max2(maximum,score[i][j]);
    }
  }

  printf("%d\n",maximum);
}
  return 0;
}