Go: package main

import "fmt"

func initialize_grid(width int,height int)[][]int{
	var grid [][]int
	for i:=0;i<height+1;i++{
		var grid_row  []int
		for j:=0;j<width+1;j++{
			grid_row = append(grid_row,0)
		}
		grid = append(grid,grid_row[:])
	}
	return grid
}

func ma(x int,y int)int{
	if x >= y{
		return x
	}else{
		return y
	}
}

func main()  {
	//Take input
	var num int
	var st1,st2 string
	var string_pairs [][]string
	fmt.Scan(&num)
	for i:=0;i<num;i++{
		var string_pair []string
		fmt.Scan(&st1)
		fmt.Scan(&st2)
		string_pair = append(string_pair,st1,st2)
		string_pairs = append(string_pairs,string_pair)
	}
	//DP
	//initialize grid
	for i:=0;i<num;i++{
		string_1 := string_pairs[i][0]
		string_2 := string_pairs[i][1]

		dp := initialize_grid(len(string_2),len(string_1))

		for j:=1;j<len(string_1)+1;j++{
			for k:=1;k<len(string_2)+1;k++{
				if string_1[j-1] == string_2[k-1]{
					dp[j][k] = dp[j-1][k-1] + 1
				}else{
					dp[j][k] = ma(dp[j-1][k],dp[j][k-1])
				}
			}
		}
		fmt.Println(dp[len(string_1)][len(string_2)])
	}
}

Python: for _ in range(int(input())):
    X = input()
    Y = input()
    dp = [[0 for y in range(len(Y)+1)] for x in range(len(X)+1)]
    for x in range(len(X) + 1):
        for y in range(len(Y) + 1):
            if x == 0 or y == 0:
                dp[x][y] = 0
            elif X[x-1] == Y[y-1]:
                dp[x][y] = dp[x-1][y-1] + 1
            else:
                dp[x][y] = max(dp[x-1][y], dp[x][y-1])
    print(dp[-1][-1])

Python: def Ics(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)

    for i in range(a):
        d = x[i]
        c2 = c1[:]
        for j in range(b):
            if d == y[j]:
                c1[j + 1] = c2[j] + 1
            elif c1[j + 1] < c1[j]:
                c1[j + 1] = c1[j]
    return (c1[-1])

q = int(input().rstrip())
r = []
for k in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    r.append(Ics(s1, s2))

print(*r, sep = "/n")

Python: print(1)

Python: #!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def main():
    num = int(stdin.readline())

    for _ in xrange(num):
        x = stdin.readline().rstrip()
        y = stdin.readline().rstrip()

        n = len(y) + 1

        cim1 = [0] * n
        for i, xi in enumerate(x, start=1):
            ci = [0] * n
            for j, yj in enumerate(y, start=1):
                if xi == yj:
                    ci[j] = cim1[j-1] + 1
                elif cim1[j] >= ci[j-1]:
                    ci[j] = cim1[j]
                else:
                    ci[j] = ci[j-1]
            cim1 = ci

        print(ci[j])


main()

Python: for i in range(int(input())):
    x = input()
    y = input()
    a=[0]
    for i in x:
        for j in range(len(a) - 1, -1, -1):
            b = y.find(i, a[j]) + 1
            if b:
                if j + 1 < len(a):
                    a[j + 1] = min(a[j + 1], b)
                else:
                    a.append(b)
    print(len(a)-1)

Python: def Ics(X, Y):
    m = len(X)
    n = len(Y)
    maxl = 0
    for i in range(m + 1):
        c[i][0] = 0
    for j in range(1, n + 1):
        c[0][j] = 0
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if(X[i] == Y[j]):
                c[i][j] = c[i - 1][j - 1] + 1
            elif(c[i - 1][j] <= c[i][j - 1]):
                c[i][j] = c[i- 1][j]
            maxl = max(maxl, c[i][j])
    return maxl

q = int(input().rstrip())
t = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    t.append(Ics(s1, s2))
print(*t, sep="\n")

Python: def Ics(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)

    for i in range(a):
        d = x[i]
        c2 = c1[:]
        for j in range(b):
            if d == y[j]:
                c1[j + 1] = c2[j] + 1
            elif c1[j + 1] < c1[j]:
                c1[j + 1] = c1[j]
    return (c1[-1])

q = int(input().rstrip())
r = []
for k in range(q):
    s1 = input().rstrip()
    s2 = input().rstrip()
    r.append(Ics(s1, s2))

print(*r, sep = "/n")

Python: # -*- coding: utf-8 -*-
"""
Created on Fri May  4 20:33:37 2018
ALDS1_10_C
@author: maezawa
"""

def longest(x, y):
    m = len(x)
    n = len(y)
    maxl = 0
    c = [[0 for _ in range(n+1)] for _ in range(m+1)]
    for i in range(m):
        for j in range(n):
            #print(i,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

q = int(input())
for i in range(q):
    x = input()
    y = input()
    print(longest(x, y))

Python: a=[]
for _ in[0]*int(input()):
 X,z=input(),[]
 for y in input():
  s=i=0
  for k in z:
   t=X.find(y,s)+1
   if t<1:break
   if t<k:z[i]=t
   s=k;i+=1
  else:
   t=X.find(y,s)+1
   if t:z+=[t]
 a+=[len(z)]
print('\n'.join(a))

Python: q = int(input())

l = []
x = ""
y = ""
"""
def lcs(yIndex, xIndex):
    global l, x, y
    if xIndex == 0 and yIndex == 0:
        return 0
    elif xIndex == 0:
        return l[yIndex - 1][0]
    elif yIndex == 0:
        return l[0][xIndex - 1]
    elif x[xIndex] == y[yIndex]:
        return 1 + l[yIndex - 1][xIndex - 1]
    else:
        if l[yIndex][xIndex - 1] > l[yIndex - 1][xIndex]:
            return l[yIndex][xIndex - 1]
        else:
            return l[yIndex - 1][xIndex]
        #return max(l[yIndex][xIndex - 1], l[yIndex - 1][xIndex])
 """
for i in range(q):
    x = input()
    y = input()
 
    yLen = len(y)
    xLen = len(x)
    l = [[-1] * xLen for j in range(yLen)]

    for j in range(yLen):
        for k in range(xLen):
            if k == 0 and j == 0:
                l[j][k] = 0
            elif k == 0:
                l[j][k] = l[j - 1][0]
            elif j == 0:
                l[j][k] =  l[0][k - 1]
            elif x[k] == y[j]:
                l[j][k] =  1 + l[j - 1][k - 1]
            else:
                if l[j][k - 1] > l[j - 1][k]:
                    l[j][k] = l[j][k - 1]
                else:
                    l[j][k] = l[j - 1][k]
            #l[j][k] = lcs(j, k)
 
    print(l[yLen- 1][xLen - 1])

Python: def main():
    n = int(input())
    for i in range(n):
        a = input()
        b = input()
        na=len(a)
        nb=len(b)
        array = [[0]*nb for i in range(na)]
        #array = [[0 for i in range(nb)] for j in range(na)]
        for i in range(na):
            for j in range(nb):
                c = 0
                if i==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                elif j==0:
                    if a[i]==b[j]:
                        array[i][j]=1
                else:
                    if a[i] == b[j]:
                        c = 1
                    array[i][j] = max(
                        array[i-1][j],
                        array[i][j-1],
                        array[i-1][j-1]+c)
        print(array[na-1][nb-1])
if __name__ == "__main__":
    main()