Go: package main

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

// define
var (
	sc = bufio.NewScanner(os.Stdin)
)

func bordersInt(in_map [][]int, invalid int) [][]int{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]int, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]int, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func bordersString(in_map [][]string, invalid string) [][]string{
	H, W := len(in_map), len(in_map[0])
	out_map := make([][]string, H+2)
	for h:=0; h<H+2; h++ {
		out_map[h] = make([]string, W+2)
		for w:=0; w<W+2; w++ {
			out_map[h][w] = invalid
		}
	}
	for h:=0; h<H; h++{
		for w:=0; w<W; w++{
			out_map[h+1][w+1] = in_map[h][w] 
		}
	}
	return out_map
}

func scanIntLine(len int) []int{
	arr := make([]int, len)
	for i:=0; i<len; i++{
		sc.Scan()
		tmp, err := strconv.Atoi(sc.Text())
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func scanStringLine(len int) []string{
	arr := make([]string, len)
	for i:=0; i<len; i++{
		sc.Scan()
		arr[i] = sc.Text()
	}
	return arr
}

func scanIntSplit(len int) []int{
	arr := make([]int, len)
	sc.Scan()
	for i, v := range strings.Split(sc.Text(), " "){
		tmp, err := strconv.Atoi(v)
		if err == nil{
			arr[i] = tmp
		}
	}
	return arr
}

func maxInt(args... int) int{
	sort.Ints(args)
	return args[len(args)-1]
}

func main(){
	var n int 
	fmt.Scan(&n)
	dp := make([][]int, 1003)
	for i:=0; i<1003; i++ {
		dp[i] = make([]int, 1003)
	}
	input_lines := scanStringLine(2*n)
	for i:=0; i<n; i++ {
		S, T := input_lines[2*i], input_lines[2*i+1]
		lenS, lenT := len(S), len(T)
		for i:=1; i<lenS+1; i++ {
			for j:=1; j<lenT+1; j++ {
				if S[i-1] == T[j-1] {
					dp[i][j] = maxInt(dp[i-1][j-1]+1, dp[i-1][j], dp[i][j-1])
				} else {
					dp[i][j] = maxInt(dp[i-1][j], dp[i][j-1])
				}
			}
		}
		fmt.Println(dp[lenS][lenT])
	}
}

C++: #include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<long long,long long>;
#define ITR(i,c) for(auto i=begin(c);i!=end(c);++i)
#define FORE(x,c) for(auto &x:c)
#define REPF(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define REP(i,n) REPF(i,0,n)
#define REPR(i,n) for(int i=(int)(n);i>=0;--i)
#define REPW(i,n) for(i=0;i<(int)(n);++i)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define SZ(c) ((int)c.size())
#define CONTAIN(c,x) (c.find(x)!=end(c))
#define OUTOFRANGE(y,x,h,w) (y<0||x<0||y>=h||x>=w)
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
#define INF (1001001001)
#define INFLL (1001001001001001001ll)
template<class T> ostream& operator << (ostream &os,const vector<T> &v) {
    ITR(i,v) os << *i << (i==end(v)-1 ? "" : "\n"); return os; }
template<class T> istream& operator >> (istream &is,vector<T> &v) {
    ITR(i,v) is >> *i; return is; }
template<class T> istream& operator >> (istream &is, pair<T,T> &p) {
        is >> p.first >> p.second; return is; }
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
//------------------------------------------------------------------------------
struct before_main_function {
    before_main_function() {
        #ifdef int
            #undef INF
            #define INF INFLL
            #define stoi stoll
        #endif
        cin.tie(0);ios::sync_with_stdio(false);
        cout<<setprecision(15)<<fixed;
        #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

int lcs(string a,string b) {
    int n=a.size(),m=b.size();
    vector<vector<int>> dp(n+1,vector<int>(m+1,0));
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(a[i]==b[j]) {
                dp[i+1][j+1]=dp[i][j]+1;
            } else {
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            }
        }
    }
    return dp[n][m];
}
signed main() {
    int q;
    cin>>q;
    while(q--) {
        string x,y;
        cin>>x>>y;
        cout<<lcs(x,y)<<endl;
    }
    return 0;
}

C++: import java.io.*;
import static java.lang.Math.max;
import static java.lang.Integer.parseInt;

class Main {
   final static PrintWriter out = new PrintWriter( System.out );

   final static BufferedReader in =
         new BufferedReader( new InputStreamReader( System.in ) );

   final static StringBuilder sb = new StringBuilder("");

   static int lcs(char[] a, char[] b){
      final int alen = a.length;
      final int blen = b.length;
      int dp[][] = new int[alen+1][blen+1];

      for(int i=0; i<alen; ++i){
         for(int j=0; j<blen; ++j){
            if(a[i] == b[j])
               dp[i+1][j+1] = dp[i][j] + 1;
            else
               dp[i+1][j+1] = max( dp[i][j+1], dp[i+1][j] );
         }
      }
      return( dp[alen][blen] );
   }

   public static void main(String[] args) throws IOException {
      final int N = parseInt( in.readLine() );
      for(int i=0; i<N; ++i){
         char[] a = in.readLine().toCharArray();
         char[] b = in.readLine().toCharArray();
         sb.append( lcs(a,b) );
         sb.append('\n');
      }
      System.out.print(sb);
   }
}

C++: #include <iostream>
#include <string>
using namespace std;
int main(void){
    int n;
    cin >> n;
    for(int i = 0;i < n;i++){
        string X,Y;
        cin >> X >> Y;
        int L[X.length()+10][Y.length()+10];
        for(int j = 0;j < X.length()+10;j++){
            for(int k = 0;k < X.length()+10;k++){
                L[j][k] = 0;
            }
        }
        for(int j = 1;j<=X.length();j++){
            for(int k = 1;k<=Y.length();k++){
                if(Y[k] == X[j]){
                    L[j][k] = 1+L[j-1][k-1];
                }
                else{
                    L[j][k] = max(L[j-1][k],L[j][k-1]);
                }
            }
        }
        cout << L[X.length()][Y.length()] << endl;
    }
return 0;
}

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

int dp[1001][1001];

int lcs(string x, string y)
{
	fill(dp[0], dp[0] + x.length() * y.length(), 0);
	for (int i = 0; i < x.length(); ++i)
	{
		for (int j = 0; j < y.length(); ++j)
		{
			if (x[i] == y[j])dp[i + 1][j + 1] = dp[i][j] + 1;
			else dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
		}
	}
	return dp[x.length()][y.length()];
}

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

C++: #define _CRT_SECURE_NO_WARNINGS

#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
#include<queue>
#include<iomanip>
#include<set>
#include<map>
#include<utility>
#include<string>
#include<vector>

using namespace std;

#define LL long long

string X,Y;
int q,Z;
int dp[1001][1001]={};

int main() {
	cin>>q;
	for(int ds=0;ds<q;ds++){
		cin>>X>>Y;
		int xs=X.size(),ys=Y.size();
		for(int i=0;i<xs;i++){
			for(int j=0;j<ys;j++){
				int tmp=0;
				if(X[i]==Y[j]){
					if(i*j==0)dp[i][j]=1;
					else dp[i][j]=dp[i-1][j-1]+1;
				}
				else {
					if(i+j==0)dp[0][0]=0;
					else if(i==0)dp[0][j]=dp[0][j-1];
					else if(j==0)dp[i][0]=dp[i-1][0];
					else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
				}
			}
		}
		cout<<dp[xs-1][ys-1]<<endl;
	}
	return 0;
}