import Control.Monad (replicateM)

main :: IO ()
main = do
    n <- readLn
    is <- replicateM n $ do
        str1 <- getLine
        str2 <- getLine
        return (str1,str2)
    mapM_ (print . lcs) is

lcs :: (String, String) -> Int
lcs (xs,ys) = lcs' (length xs) (length ys)
    where
        lcs' 0 _ = 0
        lcs' _ 0 = 0
        lcs' i j | xs !! (i-1) == ys !! (j-1) = lcs' (i-1) (j-1) + 1
                 | otherwise = lcs' i (j-1) `max` lcs' (i-1) j