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

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

lcs :: (String, String) -> Int
lcs (xs,ys) = lcs' lx ly
    where
        lx = length xs
        ly = length ys
        xs' = listArray (0,lx-1) xs
        ys' = listArray (0,ly-1) ys
        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
               