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++: #include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define rep(i, k, n) for (ll i=k; i<(ll)n; ++i)
#define REP(i, n) rep(i, 0, n)
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) REP(sz, vec.size()) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int q;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> q;
    while (q-->0) {
        string x, y; cin >> x >> y;
        vvll dp(x.size() + 1, vll(y.size() + 1, 0));
        for (int xi = 0; xi < x.size(); xi++) {
            for (int yi = 0; yi < y.size(); yi++) {
                if (x[xi] == y[yi]) dp[xi + 1][yi + 1] = dp[xi][yi] + 1;
                else dp[xi + 1][yi + 1] = max(dp[xi][yi + 1], dp[xi + 1][yi]);
            }
        }
        cout << dp[x.size()][y.size()] << '\n';
    }
    return 0;
}

C++: #include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i)
#define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i)
#define each(a,b) for(auto& (a): (b))
#define all(v) (v).begin(),(v).end()
#define len(v) (int)(v).size()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define cmx(x,y) x=max(x,y)
#define cmn(x,y) x=min(x,y)
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define sar(a,n) cout<<#a<<":";rep(pachico,n)cout<<" "<<a[pachico];cout<<endl
#define svec(v) cout<<#v<<":";rep(pachico,v.size())cout<<" "<<v[pachico];cout<<endl
#define svecp(v) cout<<#v<<":";each(pachico,v)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl
#define sset(s) cout<<#s<<":";each(pachico,s)cout<<" "<<pachico;cout<<endl
#define smap(m) cout<<#m<<":";each(pachico,m)cout<<" {"<<pachico.first<<":"<<pachico.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int> P;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<P> vp;
typedef vector<string> vs;

const int MAX_N = 100005;

const int MAX_SIZE = 52;

int LCS(const char* a, const char* b){
    int n = 0, m = 0;
    vector<int> x,y;
    for(;a[n] != '\0';n++){
        int s = a[n]-'a';
        if(s < 0){
            s = a[n]-'A'+26;
        }
        x.pb(s);
    }
    for(;b[m] != '\0';m++){
        int s = b[m]-'a';
        if(s < 0){
            s = b[m]-'A'+26;
        }
        y.pb(s);
    }
    vector<vector<int> > vec(MAX_SIZE);
    for(int j = m-1; j >= 0; --j){
        vec[y[j]].push_back(j);
    }
    vector<int> xs(n+1, INF);
    xs[0] = -INF;
    vector<P> nx(n+1,P(-INF,-INF));
    rep(i,n){
        vector<int>& ys = vec[x[i]];
        rep(j,(int)ys.size()){
            int k = lower_bound(xs.begin(),xs.end(),ys[j]) - xs.begin();
            xs[k] = ys[j];
            nx[k] = P(y[ys[j]], k-1);
        }
    }
    return lower_bound(xs.begin(),xs.end(),INF-1) - xs.begin() - 1;
}


int main()
{
    int q;
    scanf("%d",&q);
    rep(i,q){
        char x[1000], y[1000];
        scanf("%s%s",x,y);
        cout << LCS(x,y) << "\n";
    }
    return 0;
}

C++: #include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<list>
#include<stack>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>

using namespace std;
const int INF = 0x7fffffff;

int gcd(int x,int y){
  int mi,ma;
  ma = max(x,y);
  mi = min(x,y);
  if(ma % mi == 0){
    return mi;
  }
  else{
    return gcd(mi,ma % mi);
  }
}
int dp[1001][1001];

int lcs(string x,string y){

  memset(dp,0,sizeof(dp));
  int m,n,ii,jj,maxl;

  m = x.size();
  n = y.size();
  maxl = 0;
  x = ' ' + x;
  y = ' ' + y;
  for(ii=1;ii<=m;ii++){
    for(jj=1;jj<=n;jj++){

      if( x[ii] == y[jj]){
        //cout << "hoge" << endl;

        dp[ii][jj] = dp[ii - 1][jj -1] + 1;

      }
      
      else{

        dp[ii][jj] = max(dp[ii-1][jj],dp[ii][jj-1]);

      }
      maxl = max(maxl,dp[ii][jj]);      
    }
  }
  
  return maxl;

}

int main(){
  
  long ii,jj,kk;
  vector<int> a;

  int q;
  cin >> q;

  string x,y;
  int len;
  
  for(ii=0;ii<q;ii++){
    
    cin >> x >> y;
    len = lcs(x,y);

    cout << len << endl;
    
  }
  
  return 0;
}

C++: #include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define MAX 150
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<=strlen(X);i++){
    for(j=1;j<=strlen(Y);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<iostream>
#include<cstring>
using namespace std;
int q;
int main(){
  cin>>q;
  for(int z=0;z<q;z++){
    string a,b;
    cin>>a>>b;
    int n=a.size(),m=b.size();
    int dp[n+1][m+1];
    memset(dp,0,sizeof(dp));
    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]);
        }
      }
    }
    cout<<dp[n][m]<<endl;
  }
}