import Control.Monad (replicateM_)
import qualified Data.Vector as V

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


lcs :: (String,String) -> Int
lcs (xs,ys) = lcsTable (lx,ly)
    where
        lx = length xs
        ly = length ys
        xs' = V.fromList xs
        ys' = V.fromList ys
        idx (x,y) = x + y*(lx+1)
        xdi i = (i `mod` (lx+1), i `div` (lx+1))
        lcsTable = (V.map (lcs'.xdi) (V.enumFromN 0 (idx (lx,ly)+1)) V.!) . idx
        lcs' (0,_) = 0
        lcs' (_,0) = 0
        lcs' (i,j) 
          | xs' V.! (i-1) == ys' V.! (j-1) = lcsTable (i-1,j-1) + 1
          | otherwise = lcsTable (i,j-1) `max` lcsTable (i-1,j)