import Control.Monad (replicateM_)
import Data.Array (listArray, (!))
import Data.List (foldl')

main :: IO ()
main = do
    n <- readLn
    replicateM_ n $ do
        str1 <- getLine
        str2 <- getLine
        print $ lcs (str1,str2)


lcs :: (String,String) -> Int
lcs (xs,ys) = table ! lx
    where
        lx = length xs
        xs' = listArray (1,lx) xs
        table = foldl' build initial ys
        initial = listArray (0,lx) (repeat 0)
        build pre y = res
            where
                res = listArray (0,lx) [l | ix <- [0..lx]
                                          , let l | ix == 0 = 0
                                                  | xs'!ix == y = 1 + pre ! (ix-1)
                                                  | otherwise = (pre ! ix) `max` (res ! (ix-1))]