CodeEff/ECCO huggingface dataset:
# Original solution
# -*- coding: utf-8 -*-
def lcs(x, y):
    n = len(x)
    m = len(y)
    dp = [0 for j in range(m + 1)]

    for i in range(1, n + 1):
        dp_prev = dp[:]
        for j in range(1, m + 1):
            if x[i - 1] == y[j - 1]:
                dp[j] = dp_prev[j - 1] + 1
            elif dp_prev[j] < dp[j - 1]:
                dp[j] = dp[j - 1]
            else:
                dp[j] = dp_prev[j]

    return dp[m]


if __name__ == '__main__':
    import sys
    q = int(sys.stdin.readline().strip())
    for i in range(q):
        x = sys.stdin.readline().strip()
        y = sys.stdin.readline().strip()
        print((lcs(x, y)))



# Optimized solution
def m():
 e=input
 a=''
 for _ in[0]*int(e()):
  X,z=e(),[]
  for y in e():
   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+=f'\n{len(z)}'
 print((a[1:]))
if'__main__'==__name__:m()
# Original solution
def lcs(s, t):
  dp = {}
  slen = len(s)
  tlen = len(t)

  for i in range(slen + 1):
    dp[i] = {0: 0}
  for j in range(tlen + 1):
    dp[0][j] = 0

  for i in range(1, slen + 1):
    for j in range(1, tlen + 1):
      if s[i-1] == t[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1
      else:
        dp[i][j] = max(dp[i][j-1], dp[i-1][j])

  return dp[slen][tlen]

n = int(input())

for i in range(n):
  x = input()
  y = input()
  print(lcs(x, y))

# Optimized solution
def lcs(s, t):
  slen = len(s)
  tlen = len(t)
  dp = [None] * (slen + 1)

  for i in range(slen + 1):
    dp[i] = [0] * (tlen + 1)

  for i in range(1, slen + 1):
    for j in range(1, tlen + 1):
      if s[i-1] == t[j-1]:
        dp[i][j] = dp[i-1][j-1] + 1
      else:
        dp[i][j] = max(dp[i][j-1], dp[i-1][j])

  return dp[slen][tlen]

n = int(input())

for i in range(n):
  x = input()
  y = input()
  print(lcs(x, y))
# Original solution
DP_MAX = 1000
dp = [0] * (DP_MAX + 1)

for i in range(DP_MAX + 1):
  dp[i] = [0] * (DP_MAX + 1)

def lcs(s, t):
  slen = len(s)
  tlen = len(t)

  dp_i = dp[0]
  for i in range(1, slen + 1):
    dp_i_1 = dp_i
    dp_i   = dp[i]
    for j in range(1, tlen + 1):
      if s[i-1] == t[j-1]:
        dp_i[j] = dp_i_1[j-1] + 1
      else:
        dp_i[j] = max(dp_i[j-1], dp_i_1[j])

  return dp[slen][tlen]

n = int(input())

for i in range(n):
  x = input()
  y = input()
  print((lcs(x, y)))

# Optimized solution
def lcs(s, t):
  slen = len(s)
  tlen = len(t)
  dp = [0] * (slen + 1)
  dp[0] = [0] * (tlen + 1)

  for i in range(1, slen + 1):
    dp_prev = dp[i-1]
    dp_cur  = [0] * (tlen + 1)
    c = s[i-1]
    for j in range(1, tlen + 1):
      if c == t[j-1]:
        dp_cur[j] = dp_prev[j-1] + 1
      else:
        dp_cur[j] = max(dp_cur[j-1], dp_prev[j])
    dp[i] = dp_cur

  return dp[slen][tlen]

n = int(input())

for i in range(n):
  x = input()
  y = input()
  print((lcs(x, y)))
# Original solution
#!/usr/bin/env python

from sys import stdin


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

    for _ in range(n):
        x = stdin.readline().rstrip()
        y = stdin.readline().rstrip()

        m = len(x)
        n = len(y)
        #assert 1 <= m <= 1000
        #assert 1 <= n <= 1000

        c = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+1):
                if x[i-1] == y[j-1]:
                    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]
                else:
                    c[i][j] = c[i][j-1]

        print(c[-1][-1])


main()

# Optimized solution
#!/usr/bin/env python

from sys import stdin


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

    for _ in range(n):
        x = stdin.readline().rstrip()
        y = stdin.readline().rstrip()

        m = len(x)
        n = len(y)

        c = [[0]*(n+1) for _ in range(m+1)]

        cim1 = c[0]
        for i, xi in enumerate(x, start=1):
            ci = c[i]
            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(c[-1][-1])


main()
# Original solution
#!/usr/bin/env python

from sys import stdin


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

    c = [list(range(1001)) for _ in range(1001)]

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

        m = len(x)
        n = len(y)

        for i in range(m+1):
            row = c[i]
            for j in range(n+1):
                row[j] = 0

        cim1 = c[0]
        for i, xi in enumerate(x, start=1):
            ci = c[i]
            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()

# Optimized solution
#!/usr/bin/env python

from sys import stdin


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

    for _ in range(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()
# Original solution
def main():
    n = eval(input())
    for i in range(n):
        X = input()
        Y = input()
        print(lcs(X,Y))

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    c = [[0] for i in range(m+1)]
    c[0] += [0]*n
    
    for i in range(m):
        for j in range(n):
            if X[i] == Y[j]:
                c[i+1].append(c[i][j] + 1)
            else:
                if c[i][j+1] >= c[i+1][j]:
                    c[i+1].append(c[i][j+1])
                else:
                    c[i+1].append(c[i+1][j])
    return c[m][n]
    
if __name__ == "__main__":
    main()

# Optimized solution
def main():
    n = eval(input())
    for i in range(n):
        X = input()
        Y = input()
        print(lcs(X,Y))

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    r1 = [0 for i in range(n+1)]
 
    for i in range(m):
        r0 = r1[:]
        for j in range(n):
            if X[i] == Y[j]:
                r1[j+1] = r0[j] + 1
            elif r0[j+1] < r1[j]:
                r1[j+1] = r1[j]
    return r1[-1]

if __name__ == "__main__":
    main()
# Original solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
import sys
from sys import stdin
input = stdin.readline


C = []
def calc_lcs4(X, Y):
    global C
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    C = [[0]*(n+1) for _ in range(m+1)] #  ???????????§??¨???

    max_lcs = 0

    pre_row = C[0]
    for i in range(1, m):
        row = C[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                row[j] = max(pr_j, r_j1)
#                if pr_j >= r_j1:
#                    row[j] = pr_j
#                else:
#                    row[j] = r_j1
        pre_row = row

    print(max_lcs)


if __name__ == '__main__':
    num = int(eval(input()))

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        result = calc_lcs4(X, Y)

# Optimized solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
import sys
from sys import stdin
input = stdin.readline


C = []
def calc_lcs4(X, Y):
    global C
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    C = [[0]*(n+1) for _ in range(m+1)] #  ???????????§??¨???

    max_lcs = 0

    pre_row = C[0]
    for i in range(1, m):
        row = C[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row

    print(max_lcs)


if __name__ == '__main__':
    num = int(eval(input()))

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        result = calc_lcs4(X, Y)
# Original solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
import sys
from sys import stdin
input = stdin.readline


C = []
def calc_lcs4(X, Y):
    global C
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    C = [[0]*(n+1) for _ in range(m+1)] #  ???????????§??¨???

    max_lcs = 0

    pre_row = C[0]
    for i in range(1, m):
        row = C[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row

    print(max_lcs)


if __name__ == '__main__':
    num = int(eval(input()))

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        result = calc_lcs4(X, Y)

# Optimized solution
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C

????????±?????¨??????
"""
import sys
from sys import stdin
input = stdin.readline



def calc_lcs4(X, Y):
    X = ' ' + X
    Y = ' ' + Y
    m = len(X)
    n = len(Y)

    C = [[0]*(n+1) for _ in range(m+1)] #  ???????????§??¨???

    max_lcs = 0

    pre_row = C[0]
    for i in range(1, m):
        row = C[i]
        XX = X[i]
        for j, YY in enumerate(Y):
            if XX == YY:
                pr_j1 = pre_row[j - 1]
                row[j] = pr_j1 + 1
                if pr_j1+1 > max_lcs:
                   max_lcs = pr_j1 + 1
            else:
                pr_j = pre_row[j]
                r_j1 = row[j-1]
                if pr_j >= r_j1:
                    row[j] = pr_j
                else:
                    row[j] = r_j1
        pre_row = row

    print(max_lcs)


if __name__ == '__main__':
    num = int(eval(input()))

    for _ in range(num):
        X = input().strip()
        Y = input().strip()

        result = calc_lcs4(X, Y)
# Original solution
q = int(input())

lcs = {}
for i in range(1010):
    lcs[i] = {}
    for j in range(1010):
        lcs[i][j] = 0

for i in range(q):
    X = input()
    Y = input()
    for i in range(len(X)):
        for j in range(len(Y)):
            if X[i] == Y[j]:
                lcs[i+1][j+1] = lcs[i][j] + 1
            else:
                lcs[i+1][j+1] = max(lcs[i][j+1],lcs[i+1][j])
    print(lcs[len(X)][len(Y)])

# Optimized solution
q = int(input())

lcs = [[0 for j in range(1010)] for i in range(1010)]

for i in range(q):
    X = input()
    Y = input()
    for i in range(len(X)):
        for j in range(len(Y)):
            if X[i] == Y[j]:
                lcs[i+1][j+1] = lcs[i][j] + 1
            elif lcs[i][j+1] > lcs[i+1][j]:
                lcs[i+1][j+1] = lcs[i][j+1]
            else:
                lcs[i+1][j+1] = lcs[i+1][j]
    print(lcs[len(X)][len(Y)])
# Original solution
q = int(input())

lcs = [[0 for j in range(1010)] for i in range(1010)]

for i in range(q):
    X = input()
    Y = input()
    for i in range(len(X)):
        for j in range(len(Y)):
            if X[i] == Y[j]:
                lcs[i+1][j+1] = lcs[i][j] + 1
            elif lcs[i][j+1] > lcs[i+1][j]:
                lcs[i+1][j+1] = lcs[i][j+1]
            else:
                lcs[i+1][j+1] = lcs[i+1][j]
    print(lcs[len(X)][len(Y)])

# Optimized solution
q = int(input())

for i in range(q):
    X = input()
    Y = input()
    lcs1 = [0 for i in range(len(Y)+1)]
    for i in range(len(X)):
        lcs2 = lcs1+[]
        for j in range(len(Y)):
            if X[i] == Y[j]:
                lcs2[j+1] = lcs1[j] + 1
            elif lcs1[j+1] > lcs2[j]:
                lcs2[j+1] = lcs1[j+1]
            else:
                lcs2[j+1] = lcs2[j]
        lcs1 = lcs2
    print(lcs2[-1])
# Original solution
ans = {}

roop = eval(input())
for k in range(roop):
    str1 = input()
    str2 = input()
    len1 = len(str1)
    len2 = len(str2)
    
    for i in range (-1, len1):
        for j in range(-1, len2):
            if(i == -1 or j == -1):
                ans[i, j] = 0
            else:   
                if(str1[i] == str2[j]):
                    ans[i, j] = ans[i - 1, j - 1] + 1
                else:
                    ans[i, j] = max(ans[i - 1, j], ans[i, j - 1])
    print(ans[len(str1) - 1, len(str2) - 1])

# Optimized solution
roop = eval(input())
for k in range(roop):
    str1 = input()
    str2 = input()
    len1 = len(str1) + 1
    len2 = len(str2) + 1
    ans = [None] * (len1)
    for i in range(len1):
        ans[i] = [None] * (len2)
    for i in range(len1):
        ans[i][0] = 0
    for j in range(len2):
        ans[0][j] = 0
    for i in range (1, len1):
        for j in range(1, len2):
            if(str1[i - 1] == str2[j - 1]):
                ans[i][j] = ans[i -1][j - 1] + 1
            else:
                ans[i][j] = max(ans[i - 1][j], ans[i][j - 1])
    print(ans[len1 - 1][len2 - 1])
# Original solution
ans = [None] * 1001
for i in range(1001):
    ans[i] = [None] * 1001
for i in range(1001):
    ans[i][0] = 0
for j in range(1001):
    ans[0][j] = 0
    
roop = eval(input())
for k in range(roop):
    str1 = input()
    str2 = input()
    len1 = len(str1) + 1
    len2 = len(str2) + 1
    for i in range (1, len1):
        for j in range(1, len2):
            if(str1[i - 1] == str2[j - 1]):
                ans[i][j] = ans[i -1][j - 1] + 1
            else:
                ans[i][j] = max(ans[i - 1][j], ans[i][j - 1])
    print(ans[len1 - 1][len2 - 1])

# Optimized solution
n = eval(input())
for k in range(n):
    str1 = input()
    str2 = input()
    
    after = [0] * (len(str2) + 1)
    
    for i in range(1, len(str1) + 1):
        before = after + []
        for j in range(1, len(str2) + 1):
            if str1[i - 1] == str2[j - 1]:
                after[j] = before[j - 1] + 1
            else:
                after[j] = max(before[j], after[j - 1])
    print(after[j])
# Original solution
n = eval(input())
for k in range(n):
    str1 = input()
    str2 = input()
    
    after = [0] * (len(str2) + 1)
    
    for i in range(1, len(str1) + 1):
        before = after + []
        for j in range(1, len(str2) + 1):
            if str1[i - 1] == str2[j - 1]:
                after[j] = before[j - 1] + 1
            else:
                after[j] = max(before[j], after[j - 1])
    print(after[j])

# Optimized solution
n = eval(input())
for k in range(n):
    str1 = input()
    str2 = input()
    
    after = [0] * (len(str2) + 1)
    
    for i in range(1, len(str1) + 1):
        before = after + []
        for j in range(1, len(str2) + 1):
            if str1[i - 1] == str2[j - 1]:
                after[j] = before[j - 1] + 1
            elif after[j - 1] > before[j]:
                after[j] = after[j - 1]
    print(after[j])
# Original solution
import sys
def lcs(X, Y):
    c = [0 for _ in range(len(Y) + 1)]

    for i in X:
        tmp = c[:]
        for ji, yc in enumerate(Y):
            j = ji + 1
            if i == yc:
                c[j] = tmp[j - 1] + 1
            else:
                c[j] = max(tmp[j], c[j - 1])
    return c[-1]

n = int(eval(input()))

for i in range(n):
    X = sys.stdin.readline()[:-1]
    Y = sys.stdin.readline()[:-1]
    print((lcs(X, Y)))

# Optimized solution
import sys

def lcs(X, Y):
    c = [0 for _ in range(len(Y) + 1)]
    for i in X:
        tmp = c[:]
        for ji, yc in enumerate(Y):
            j = ji + 1
            if i == yc:
                c[j] = tmp[j - 1] + 1
            elif c[j] < c[j - 1]:
                c[j] = c[j - 1]
    return c[-1]

n = int(eval(input()))

for i in range(n):
    X = sys.stdin.readline()[:-1]
    Y = sys.stdin.readline()[:-1]
    print((lcs(X, Y)))
# Original solution
import sys

n = eval(input())
for i2 in range(n):
    seq1 = input()
    seq2 = input()
    
    a,b = len(seq1)+1, len(seq2)+1
    length = [[0 for i in range(b)] for j in range(a)]

    for i in range(a):
        for j in range(b):
            if i==0 or j==0:
                length[i][j]=0
            else:
                if seq1[i-1] == seq2[j-1]:
                    length[i][j] = length[i-1][j-1] + 1
                else:
                    length[i][j] = max(length[i-1][j], length[i][j-1])
    print(length[a-1][b-1])

# Optimized solution
import sys

def longestcommonsubsequence(seq1, seq2):
    a,b = len(seq1)+1, len(seq2)+1
    length = [[0 for i in range(b)] for j in range(a)]

    for i in range(a):
        for j in range(b):
            if i==0 or j==0:
                pass
                length[i][j]=0
            else:
                if seq1[i-1] == seq2[j-1]:
                    length[i][j] = length[i-1][j-1] + 1
                else:
                    length[i][j] = max(length[i-1][j], length[i][j-1])
    return length[a-1][b-1]

n = eval(input())
for i2 in range(n):
    seq1 = input()
    seq2 = input()

    print(longestcommonsubsequence(seq1, seq2))
# Original solution
import sys

def longestcommonsubsequence(seq1, seq2):
    a,b = len(seq1), len(seq2)
    length = [[0 for i in range(b+1)] for j in range(a+1)]

    for i in range(a):
        e1 = seq1[i]
        tmp = length[i]
        x = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x[j+1]=tmp[j] + 1
            else:
                x[j+1]=max(tmp[j+1], x[j])
        length[i+1]=x
    return length[a][b]

n = eval(input())
for i2 in range(n):
    seq1 = input()
    seq2 = input()

    print(longestcommonsubsequence(seq1, seq2))

# Optimized solution
import sys

def longestcommonsubsequence(seq1, seq2):
    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1
        x1 = [0]
        for j in range(b):
            if e1 == seq2[j]:
                x1.append(x2[j] + 1)
            else:
                x1.append(max(x2[j+1], x1[j]))
    return x1[-1]

n = eval(input())
for i2 in range(n):
    seq1 = input()
    seq2 = input()

    print(longestcommonsubsequence(seq1, seq2))
# Original solution
import sys

def longestcommonsubsequence(seq1, seq2):
    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1
        x1 = [0]
        for j in range(b):
            if e1 == seq2[j]:
                x1.append(x2[j] + 1)
            else:
                x1.append(max(x2[j+1], x1[j]))
    return x1[-1]

n = eval(input())
for i2 in range(n):
    seq1 = input()
    seq2 = input()

    print(longestcommonsubsequence(seq1, seq2))

# Optimized solution
import sys

def longestcommonsubsequence(seq1, seq2):
    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1
        x1 = [0 for i in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1]=x2[j] + 1
            else:
                x1[j+1]=max(x2[j+1], x1[j])
    return x1[-1]

n = eval(input())
for i2 in range(n):
    seq1 = input()
    seq2 = input()

    print(longestcommonsubsequence(seq1, seq2))
# Original solution
import sys

n = eval(input())
for i2 in range(n):
    seq1 = input()
    seq2 = input()

    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1
        x1 = [0 for i in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1]=x2[j] + 1
            else:
                x1[j+1]=max(x2[j+1], x1[j])
    print(x1[-1])

# Optimized solution
import sys

def longestcommonsubsequence():
    seq1 = input()
    seq2 = input()

    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1
        x1 = [0 for i in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1]=x2[j] + 1
            else:
                x1[j+1]=max(x2[j+1], x1[j])
    return x1[-1]

n = eval(input())
for i2 in range(n):

    print(longestcommonsubsequence())
# Original solution
import sys

def longestcommonsubsequence():
    seq1 = input()
    seq2 = input()

    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    i=0
    for e1 in seq1:
        x2 = x1
        x1 = [0 for i in range(b+1)]
        j=0
        for e2 in seq2:
            if e1 == e2:
                x1[j+1]=x2[j] + 1
            else:
                x1[j+1]=max(x2[j+1], x1[j])
            j += 1
        i += 1
    return x1[-1]

n = eval(input())
for i2 in range(n):

    print(longestcommonsubsequence())

# Optimized solution
import sys

def longestcommonsubsequence():
    seq1 = input()
    seq2 = input()

    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    i=0
    for e1 in seq1:
        x2 = x1
        x1 = [0 for i in range(b+1)]
        j=0
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1]=x2[j] + 1
            else:
                x1[j+1]=max(x2[j+1], x1[j])
        i += 1
    return x1[-1]

n = eval(input())
for i2 in range(n):

    print(longestcommonsubsequence())
# Original solution
import sys

def longestcommonsubsequence():
    seq1 = input()
    seq2 = input()

    a,b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1
        x1 = [0 for i2 in range(b+1)]
        tmp = 0
        for j in range(b):
            if e1 == seq2[j]:
                tmp = x2[j] + 1
            else:
                tmp = max(x2[j+1], tmp)
            x1[j+1] = tmp
    return x1[-1]

n = eval(input())
for i2 in range(n):

    print(longestcommonsubsequence())

# Optimized solution
import sys

def longestcommonsubsequence():
    seq1 = input()
    seq2 = input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            else:
                x1[j+1] = max(x1[j+1], x1[j])
    return x1[-1]

n = eval(input())
for i2 in range(n):

    print(longestcommonsubsequence())
# Original solution
import sys

def longestcommonsubsequence():
    seq1 = input()
    seq2 = input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            else:
                x1[j+1] = max(x1[j+1], x1[j])
    return x1[-1]

n = eval(input())
for i2 in range(n):

    print(longestcommonsubsequence())

# Optimized solution
import sys

def longestcommonsubsequence():
    seq1 = input()
    seq2 = input()

    a, b = len(seq1), len(seq2)
    x1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = seq1[i]
        x2 = x1+[]
        #x1 = [0 for i2 in range(b+1)]
        for j in range(b):
            if e1 == seq2[j]:
                x1[j+1] = x2[j] + 1
            elif x1[j+1]<x1[j]:
                x1[j+1] = x1[j]
    return x1[-1]

n = eval(input())
for i2 in range(n):

    print(longestcommonsubsequence())