import qualified Data.MemoCombinators as M

{- First trial -}
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)

{- Second trial -}
{- but most of codes come from RosettaCode... -}
lcs' = memoize lcsm
       where
         lcsm [] _ = []
         lcsm _ [] = []
         lcsm ax@(x:xs) ay@(y:ys)
           | x == y    = x:(lcs' xs ys)
           | otherwise = maxl (lcs' ax ys) (lcs' xs ay)

maxl x y = if length x > length y then x else y
memoize = M.memo2 mString mString
mString = M.list M.char

{- Parse input -}
main = do
  getLine
  inputs <- fmap lines getContents
  let targets = zip (takeOnlyOdd inputs) (takeOnlyEven inputs)
  mapM_ putStrLn $ map (\(x,y) -> show . length $ lcs' x y) 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