output_description: For each dataset, print the length of LCS of $X$ and $Y$ in a line.
input_description: The input consists of multiple datasets. In the first line, an integer $q$
  which is the number of datasets is given. In the following $2 \times q$ lines,
  each dataset which consists of the two sequences $X$ and $Y$ are given.
attempt: num = int(input())
  for i in range(num):
      X = " " + input()
      Y = " " + input()
      lx = len(X)
      ly = len(Y)
      T = [0] * ly
      for j in range(1, lx):
          C = T[:]
          for k in range(1, ly):
              k1 = k - 1
              if X[j] == Y[k]:
                  T[k] = C[k1] + 1
              elif C[k] > T[k1]:
                  T[k] = C[k]
              else:
                  T[k] = T[k1]
          print(T[k])
  
problem_description: Longest Common Subsequence
  
  For given two sequences $X$ and $Y$, a sequence $Z$ is a common subsequence of
  $X$ and $Y$ if $Z$ is a subsequence of both $X$ and $Y$. For example, if $X =
  \\{a,b,c,b,d,a,b\\}$ and $Y = \\{b,d,c,a,b,a\\}$, the sequence $\\{b,c,a\\}$
  is a common subsequence of both $X$ and $Y$. On the other hand, the sequence
  $\\{b,c,a\\}$ is not a longest common subsequence (LCS) of $X$ and $Y$, since
  it has length 3 and the sequence $\\{b,c,b,a\\}$, which is also common to both
  $X$ and $Y$, has length 4. The sequence $\\{b,c,b,a\\}$ is an LCS of $X$ and
  $Y$, since there is no common subsequence of length 5 or greater.
  
  Write a program which finds the length of LCS of given two sequences $X$ and
  $Y$. The sequence consists of alphabetical characters.
samples: [{"input": "3\n    abcbdab\n    bdcaba\n    abc\n    abc\n    abc\n    bc", "output": "4\n    3\n    2"}]