def lcs(A,B):
  n,m = len(A), len(B)
  dp = [ [0]*(m+1) for _ in range(n+1) ]

  for i in range(1,n+1):
    a = A[i-1]
    for j in range(1,m+1):
      b = B[j-1]
      if a == b:
        # dp[i][j] = max(dp[i-1][j], min(dp[i-1][j-1], dp[i][j-1])+1)
        dp[i][j] = dp[i-1][j-1] + 1
      else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])

  return dp[n][m]

n = int(input())
for _ in range(n):
  a = input()
  b = input()
  print(lcs(a,b))