Go: package main

import (
	"bufio"
	"bytes"
	"fmt"
	"io"
	"os"
	"strconv"
	"strings"
)

const N = 1001

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

func lcs(x, y string) int {
	var c [N][N]int
	m := len(x)
	n := len(y)
	var maxl int

	x = " " + x
	y = " " + y

	for i := 1; i <= m; i++ {
		for 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(maxl, c[i][j])
		}
	}
	return maxl
}

func answer(reader io.Reader) string {
	sc := bufio.NewScanner(reader)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	q, _ := strconv.Atoi(sc.Text())

	var out bytes.Buffer
	for i := 0; i < q; i++ {
		sc.Scan()
		s1 := sc.Text()
		sc.Scan()
		s2 := sc.Text()
		out.WriteString(fmt.Sprintf("%d\n", lcs(s1, s2)))
	}
	return strings.TrimRight(out.String(), "\n")
}

func main() {
	fmt.Println(answer(os.Stdin))
}

C++: #include <stdio.h>
#include <stdint.h>
#include <iostream>
#include <fstream>
#include <cassert>
#include <climits>
#include <vector>
#include <memory>
using namespace std;

#define DEBUG (0)

#if DEBUG
#define DPRINTF(...) do { \
    printf("D(L%d) %s: ", __LINE__, __func__); \
    printf(__VA_ARGS__); \
  } while (false)
#else
#define DPRINTF(...)
#endif // DEBUG


vector<string> makeSubsequences(string str, int length)
{
  if (length == 0)
    return vector<string>();

  DPRINTF("str %s  length %d\n", str.c_str(), length);
  assert(0 <= length && length <= str.length());

  vector<string> subsequences;

  if (length == 1)
  {
    for (int i = 0; i < str.length(); i++)
    {
      subsequences.push_back(str.substr(i, 1));
    }

    return subsequences;
  }

  for (int i = 0; i <= str.length() - length; i++)
  {
    const string substr = str.substr(i + 1, str.length() - (i + 1));
    vector<string> strs = makeSubsequences(substr, length - 1);

    for (string s : strs)
      subsequences.push_back(str[i] + s);
  }

  return subsequences;
}


bool isFindSubseq(string str, string subseq)
{
  DPRINTF("str %s  subseq %s\n", str.c_str(), subseq.c_str());

  assert(str.length() > 0 && subseq.length() > 0);

  int j = 0;

  for (int i = 0; i < str.length(); i++)
  {
    if (str[i] == subseq[j])
      j++;

    if (j == subseq.length())
      return true;
  }

  return false;
}


int setLCSlen(string strShort, string strLong, int idx, int *pLength)
{
  DPRINTF("strLong %s  strShort %s  idx %d\n", strLong.c_str(), strShort.c_str(), idx);

  assert(strShort.length() && strLong.length() && idx >= 0 && pLength);

  if (idx == 0)
  {
    const string s = strShort.substr(0, 1);

    if (isFindSubseq(strLong, s))
      pLength[0] = 1;
    else
      pLength[0] = 0;

    return pLength[0];
  }

  if (!pLength[idx-1])
    setLCSlen(strShort, strLong, idx-1, pLength);

  const string sub = strShort.substr(0, idx);

  vector<string> candidates = makeSubsequences(sub, pLength[idx-1]);

  for (string &s : candidates)
    s = s + strShort[idx];

#if DEBUG
  DPRINTF("Candidates\n");
  for (string s : candidates)
    DPRINTF(" - %s\n", s.c_str());
#endif // DEBUG

  for (string s : candidates)
  {
    if (isFindSubseq(strLong, s))
    {
      pLength[idx] = s.length();
      break;
    }
  }

  if (!pLength[idx])
    pLength[idx] = pLength[idx-1];

  DPRINTF("pLength[%d] %d\n", idx, pLength[idx]);

  return pLength[idx];
}


int getLCSlen(string s0, string s1)
{
  const string* pStrLong;
  const string* pStrShort;

  if (s0.length() < s1.length())
  {
    pStrShort = &s0;
    pStrLong = &s1;
  }
  else
  {
    pStrShort = &s1;
    pStrLong = &s0;
  }

  int *pLongestLens = new int[pStrShort->length()];

  // init
  for (int i = 0; i < pStrShort->length(); i++)
    pLongestLens[i] = 0;

  const int longest = setLCSlen(*pStrShort, *pStrLong, pStrShort->length() - 1, pLongestLens);

  delete [] pLongestLens;

  return longest;
}


int main()
{
  int numOfPair;
  cin >> numOfPair; cin.ignore();

  DPRINTF("num of pair %d\n", numOfPair);

  for (int i = 0; i < numOfPair; i++)
  {
    string str0, str1;
    cin >> str0 >> str1; cin.ignore();

    DPRINTF("str0 %s  str1 %s\n", str0.c_str(), str1.c_str());

    cout << getLCSlen(str0, str1) << endl;
  }

  return 0;
}

C++: #include<iostream>
#include<algorithm>
#include<string>
using namespace std;

int C[1001][1001];
string N1, N2;

int lcs()
{
	int m = N1.size();
	int n = N2.size();
	int maxl = 0;

	N1 = " " + N1;
	N2 = " " + N2;

	for (int i = 1; i <= m; i++)
		C[i][0] = 0;
	for (int i = 1; i <= n; i++)
		C[0][i] = 0;

	for (int i = 1; i <= m; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (N1[i] == N2[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(maxl, C[i][j]);
		}
	}

	return maxl;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	int q;

	cin >> q;
	for (int i = 0; i < q; i++)
	{
		cin >> N1 >> N2;
		cout << lcs() << endl;
	}
		
	return 0;                                                                            
}

C++: #include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
#include <complex>
#include <utility>
#include <map>
#include <inttypes.h>

int LCS(std::string s,std::string t){
    int n,m,c[n+1][m+1];
    n=s.size();
    m=t.size();
    int maxlen=0;
    for(int i=0;i<n;i++){
        c[i][0]=0; 
    }
    for(int i=0;i<m;i++){
        c[0][i]=0;
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(s[i]==t[i]){
                c[i][j]=c[i-1][j-1]+1;
            }else{
                c[i][j]=std::max(c[i-1][j],c[i][j-1]);
            }
            maxlen=std::max(c[i][j],maxlen);
        }
    }
    return maxlen;
}
int main(){
	int N;
    
    std::cin >> N;
    std::string s1,s2;
    for(int i=0;i<N;i++){
        std::cin >> s1 >> s2;
        std::cout << LCS(s1,s2) <<std::endl;
    }
        
    
    return 0;
}

C++: #include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <ctime>
#include <cstdlib>

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

typedef long long ll;

int main()
{
	int n, dp[1024][1024];
	string a, b;
	cin >> n;
	
	while(n)
	{
		n--;
		memset(dp, 0, sizeof(dp));

		cin >> a;
		cin >> b;

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

		cout << dp[a.size()][b.size()] << endl;
	}
}

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

using namespace std;

static const int N = 1000;

int lcs(string X, string Y) {
    int C[N + 1][N + 1];
    int m = X.size();
    int n = Y.size();

    X = ' ' + X;
    Y = ' ' + Y;
    for (int i = 0; i <= m; i++) {
        C[i][0] = 0;
    }
    for (int i = 1; i <= n; i++) {
        C[0][i] = 0;
    }
    int maxl = -100;
    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(maxl, C[i][j]);
        }
    }

    return maxl;
}

int main() {
    int n;
    string X, Y;

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> X >> Y;
        cout << lcs(X, Y) << endl;
    }

    return 0;
}