leng :: Int
leng = 1001

getPos :: Int -> Int -> Int
getPos y x = y * leng + x

lcs :: String -> String -> Int -> Int
lcs in1 in2 = (map lcs_func [0 ..] !!)
    where
      lcs_func n
          | (length in1) == 1 || (length in2) == 1 = if (head in1) == (head in2) then 1 else 0
          | (head in1) == (head in2) = (lcs (tail in1) (tail in2) (getUpLeft n)) + 1
          | otherwise = max (lcs (tail in1) in2 (getUp n)) (lcs in1 (tail in2) (getLeft n))
      getUp n = n - leng
      getLeft n = n - 1
      getUpLeft n = n - leng - 1

solve :: String -> String -> Int
solve in1 in2 = lcs in1 in2 (getPos ((length in1) - 1) ((length in2) - 1))

input :: Int -> IO ()
input n
    | n == 0 = return ()
    | otherwise = do
  str1 <- getLine
  str2 <- getLine
  putStrLn $ show $ solve str1 str2
  input $ n-1
                         

main :: IO()
main = do
  n <- readLn
  input n