Go: package main

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

type Position struct {
	X int
	Y int
}

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 {
	return lcs(strX, strY, Position{0, 0}, make(map[Position]int))
}

func lcs(strX string, strY string, position Position, memo map[Position]int) int {
	if position.X >= len(strX) || position.Y >= len(strY) {
		return 0
	}
	if v, ok := memo[position]; ok {
		return v
	}
	if strX[position.X] == strY[position.Y] {
		result := lcs(strX, strY, Position{position.X + 1, position.Y + 1}, memo)
		memo[position] = result + 1
		return memo[position]
	} else {
		result1 := lcs(strX, strY, Position{position.X + 1, position.Y}, memo)
		result2 := lcs(strX, strY, Position{position.X, position.Y + 1}, memo)
		var result int
		if result1 > result2 {
			result = result1
		} else {
			result = result2
		}
		memo[position] = result
		return result
	}
}

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++: #ifdef BUILT_LOCAL

#include "niklib.h"

#endif

#include <iostream>
#include <utility>
#include <numeric>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <map>
#include <cmath>
#include <set>
#include <list>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
constexpr ll mod = 1000000007;

typedef long long num;

#define bs(n) (1ll<<(ll)(n))
#define rep(i, n) for(ll (i) = 0;(i) < (n);(i)++)
#define rrep(i, n) for(ll (i) = 1;(i) <= (n);(i)++)

int v[1010][1010], f[1010][1010][2];

int lcs2(string &a, string &b) {
    memset(v, 0, sizeof(int[1010][1010]));
    memset(f, 0, sizeof(int[1010][1010][2]));
    int n = a.length(), m = b.length(), ri = 0, rj = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i] == b[j] && v[i + 1][j + 1] < v[i][j] + 1) {
                v[i + 1][j + 1] = v[i][j] + 1;
                f[i + 1][j + 1][0] = i;
                f[i + 1][j + 1][1] = j;
            }
            if (v[i + 1][j] < v[i][j]) {
                v[i + 1][j] = v[i][j];
                f[i + 1][j][0] = i;
                f[i + 1][j][1] = j;
            }
            if (v[i][j + 1] < v[i][j]) {
                v[i][j + 1] = v[i][j];
                f[i][j + 1][0] = i;
                f[i][j + 1][1] = j;
            }
        }
    }
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            if (v[ri][rj] < v[i][j]) {
                ri = i;
                rj = j;
            }
    string ret;
    int rn = v[ri][rj];
    while (ri != 0 && rj != 0) {
        if (f[ri][rj][0] == ri - 1 && f[ri][rj][1] == rj - 1) {
            ret.push_back(a[ri]);
        }
        int rii = f[ri][rj][0];
        int rjj = f[ri][rj][1];
        ri = rii;
        rj = rjj;
    }
    return rn;
}


int main() {
    int q;
    cin >> q;
    string a, b;
    rep(i, q) {
        cin >> a >> b;
        cout << lcs2(a, b) << endl;
    }
}

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;                                                                            
}