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) = lcsTable (lx,ly)
    where
        lx = length xs
        ly = length ys
        xs' = listArray (0,lx-1) xs
        ys' = listArray (0,ly-1) ys
        idx (x,y) = x + y*(lx+1)
        xdi i = (i `mod` (lx+1), i `div` (lx+1))
        lcsTable = (listArray (0,idx (lx,ly)) ls !) . idx
        ls = map (lcs' . xdi) [0..]
        lcs' (0,_) = 0
        lcs' (_,0) = 0
        lcs' (i,j) 
          | xs'!(i-1) == ys'!(j-1) = lcsTable (i-1,j-1) + 1
          | otherwise = lcsTable (i,j-1) `max` lcsTable (i-1,j)