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: ascii_letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
  
  
  def llcs(x, y):
      pm = dict((zip(ascii_letters, [0] * 52)))
      for c in pm:
          for i, xc in enumerate(x):
              if c == xc:
                  pm[c] |= 1 << i
  
      V = (1 << len(x)) - 1
  
      for yc in y:
          V = (V + (V & pm[yc])) | (V & ~pm[yc])
  
      ans = bin(V)[-len(x) :].count("0")
  
      return ans
  
  
  from sys import stdin
  
  
  def solve():
      file_input = stdin
      q = int(file_input.readline())
      for i in range(q):
          s1 = file_input.readline().rstrip()
          s2 = file_input.readline().rstrip()
          print(llcs(s1, s2))
  
  
  solve()
  
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"}]