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: def lcs(list1,list2):
      f=[[0 for x in range(len(list1)+1)]for y in range(len(list2)+1)]#表の確保
  
      for j in range(len(list1)):
          if list1[j]==list2[0]:
              f[j][0]=1
      for j in range(len(list2)):
          if list1[0]==list2[j]:
              f[0][j]=1
              
      for j in range(1,len(list1)):
          for k in range(1,len(list2)):
              if list1[j]==list2[k]:
                  f[j][k]=f[j-1][k-1]+1
              else:
                  f[j][k]=max(f[j-1][k],f[j][k-1])
  
      print(f[len(list1)-1][len(list2)-1])
  
  
  
  n=int(input())
  l=[]
  
  for i in range(n*2):
      str=input()
      l+=[list(str)]
  l[0].pop()
  
  i=0
  while True:#(文字列の数/2)回繰り返す
      if i>2*n-2:
          break
      lcs(l[i],l[i+1])
      i+=2
  
  
  
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"}]