lcs :: (String,String) -> Int -> Int
lcs ([],_) n = n
lcs (_,[]) n = n
lcs (ax@(x:xs),ay@(y:ys)) n
  | x == y    = lcs (xs,ys) (n+1)
  | otherwise = max (lcs (ax,ys) n) (lcs (xs,ay) n)
 
main = do
  getLine
  inputs <- fmap lines getContents
  let targets = zip (takeOnlyOdd inputs) (takeOnlyEven inputs)
  mapM_ putStrLn $ map (\x -> show $ lcs x 0) targets
 
takeOnlyEven :: [a] -> [a]
takeOnlyEven xs = map snd . filter (\(i, n) -> i `mod` 2 == 0) $ zip [1..] xs
takeOnlyOdd :: [a] -> [a]
takeOnlyOdd xs = map snd . filter (\(i, n) -> i `mod` 2 == 1) $ zip [1..] xs