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 <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define MAX 1001
void solve(void);
int q,count[MAX][MAX]={},xlength,ylength;
char X[MAX],Y[MAX];
 
void solve(void){
  int i,j;
 
  xlength=strlen(X);
  ylength=strlen(Y);
   
  for(i=1;i<=xlength;i++){
    for(j=1;j<=ylength;j++){
      if(X[i-1]==Y[j-1]) count[i][j]=count[i-1][j-1]+1;
      else if(count[i-1][j]>=count[i][j-1]) count[i][j]=count[i-1][j];
      else count[i][j]=count[i][j-1];
    }
  }
}
     
int main()
{
  int i;
   
  scanf("%d",&q);
 
  for(i=1;i<=q;i++){
    scanf("%s",X);
    scanf("%s",Y);
    solve();
    printf("%d\n",count[xlength][ylength]);
  }
 
  /*for(i=0;i<q;i++){
    printf("%d\n",count[][]);
    }*/
 
  return 0;
}

C++: #include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

short checkTable[1001][1001];

int tmp_max=0;


void calc(int index,char pattern[],char to_search[],int to_search_length){

	for(int i=to_search_length-1;i>=0;i--){
		if(to_search[i]==pattern[index]){
			checkTable[index][i]=1;
			if(pattern[index+1]!='\0' && i < to_search_length-1){
				checkTable[index][i] = checkTable[index+1][i+1] + checkTable[index][i];
			}
		}else{
			if(i != to_search_length-1){
				if(pattern[index+1] != '\0'){
					checkTable[index][i]=(checkTable[index+1][i]>checkTable[index][i+1])
							?checkTable[index+1][i]:checkTable[index][i+1];

				}else{
					checkTable[index][i]=(checkTable[index][i+1]>0)?checkTable[index][i+1]:0;
				}
			}else{
				if(pattern[index+1] != '\0'){
					checkTable[index][i]=(checkTable[index+1][i]>0)?checkTable[index+1][i]:0;
				}else{
					checkTable[index][i] = 0;
				}
			}
		}
		tmp_max = (tmp_max >= checkTable[index][i])?tmp_max:checkTable[index][i];
	}
}

int main(){
	for(int i=0;i<1000;i++){
		for(int k=0; k < 1000; k++)checkTable[i][k]= -1;
	}

	int q,left_length,right_length;
	char left[1001],right[1001];

	scanf("%d",&q);

	for(int i=0;i<q;i++){
		left_length=0;
		right_length=0;
		scanf("%s %s",left,right);
		for(int k=0;left[k]!='\0';k++)left_length++;
		for(int k=0;right[k]!='\0';k++)right_length++;

		if(right_length>=left_length){

			for(int k=left_length-1;k>=0;k--)calc(k,left,right,right_length);
		}else{

			for(int k=right_length-1;k>=0;k--)calc(k,right,left,left_length);
		}
		printf("%d\n",tmp_max);
		tmp_max=0;
	}

    return 0;
}

C++: //#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <cmath>
#include <ios>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
//#include <windows.h>
using namespace std;
template<class T> using V = vector<T>;
template<class T> using VV = V<V<T>>;
template<class T> using VVV = V<VV<T>>;
template<class T> using G = greater<T>;
template<class T1, class T2> using P = pair<T1, T2>;
using I = int;
using D = double;
using B = bool;
using C = char;
using S = string;
using LL = long long;
using LD = long double;
using ULL = unsigned long long;
using PII = P<I, I>;
using VPII = V<PII>;
using PLL = P<LL, LL>;
using VPLL = V<PLL>;
using VI = V<I>;
using VVI = VV<I>;
using VLL = V<LL>;
using VVLL = VV<LL>;
using VC = V<C>;
using VVC = VV<C>;
using VS = V<S>;
using VVS = VV<S>;
using VB = V<B>;
using VVB = VV<B>;
#define REP(type, i, n) for (type i = 0; i < (type)(n); ++i)
#define REP2(type, i, m, n) for (type i = (m); i < (type)(n); ++i)
#define REPR(type, i, n) for (type i = (n)-1; i >= 0; --i)
#define REPR2(type, i, m, n) for (type i = (n)-1; i >= (m); --i)
#define REPx(x, a) for(auto x : a)
#define ALL(a) a.begin(), a.end()
#define SORT(a) sort(ALL(a))
#define SORTR(a, type) sort(ALL(a), G<type>())
#define REVERSE(a) reverse(ALL(a))
#define SIZE(a, type) ((type)(a).size())
#define bit_search(bit, n) REP(LL, bit, 1LL<<(n))
#define bit_check(bit, i) ((bit>>(i)) & 1)
#define setpre(n) fixed << setprecision((n))
#define UNIQUE(a) do {SORT(a); (a).erase(unique(ALL(a)), (a).end());} while(0)
#define MAX(a) *max_element(ALL(a))
#define MIN(a) *min_element(ALL(a))
#define bisect_left(a, x) lower_bound(ALL(a), (x)) - a.begin()
#define bisect_right(a, x) upper_bound(ALL(a), (x)) - a.begin()
#define INPUT(a) REPx(&x, a) cin >> x;
#define INPUTP(a) REPx(&x, a) cin >> x.first >> x.second;
#define OUTPUT_PERMUTATION(n) do{VI v(n); iota(ALL(v), 1); do{REPx(x, v) cout << x << " "; ENDL} while(next_permutation(ALL(v)));} while(0);
#define MAKE_PERMUTATION(n, PER) do{VVI a(fact(n), VI(n)); int idx = 0; VI v(n); iota(ALL(v), 1); do{REP(roop, n) a[idx][roop] = v[roop]; idx++;} while(next_permutation(ALL(v))); PER = a;} while(0); // int fact(), VVI PERを宣言しておく、n=10が限界(500 ms)
#define ENDL cout << endl;

const int INF = 2e9;
const LL MOD = 1e9 + 7;

template<class T> using PRIORITY_QUEUE = priority_queue< T, V<T>, G<T> >;
template<class T> inline bool chmin(T &a, T b){if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){if (a < b) {a = b; return true;} return false;}
template<class T> inline void debug1(V<T> A){REP(int, i, SIZE(A, int)){if (A[i] == INF) cout << "I "; else cout << A[i] << " ";}}
template<class T> inline void debug2(VV<T> A){REP(int, i, SIZE(A, int)){REP(int, j, SIZE(A[0], int)){if (A[i][j] == INF) cout << "I "; else cout << A[i][j] << " ";}ENDL}}

int LCS(auto A, auto B)
{
  // 配列 A、B のLCS(Longest Common Subsequence)を求める
  int N = SIZE(A, int), M = SIZE(B, int);
  VVI dp(N+1, VI(M+1, 0));
  REP(int, i, N) REP(int, j, M)
  {
    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
    if (A[i] == B[j]) dp[i+1][j+1] = dp[i][j] + 1;
  }
  return dp[N][M];
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  int q;
  cin >> q;
  while(q--)
  {
    string x, y;
    cin >> x >> y;
    cout << LCS(x, y) << endl;
  }

  return 0;
}