{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Array.Unboxed
import Data.Functor
import Data.List
import qualified Data.ByteString.Char8  as B
import qualified Data.IntMap.Strict     as IntMap
import qualified Data.Vector.Unboxed    as VU

main :: IO ()
main = do
  n <- readLn
  xs <- replicateM n get2Lines :: IO [(String, String)]
  mapM_ (print . uncurry rowdp') xs 

get2Lines :: IO (String, String)
get2Lines = do
  a <- getLine
  b <- getLine
  return (a, b)

rowdp' :: String -> String -> Int
rowdp' xs ys = last $ foldl' scanY headRow xs
  where
    m = length ys
    headRow = replicate (m + 1) 0 :: [Int]
    scanY :: [Int] -> Char -> [Int]
    scanY prevRow x = myscanl' f 0 yvprev
      where
        yvprev = zip3 ys prevRow $ tail prevRow
        f :: Int -> (Char, Int, Int) -> Int
        f v (y, a, b) = if x == y 
                        then 1 + a
                        else max b v

myscanl'           :: (b -> a -> b) -> b -> [a] -> [b]
myscanl' = scanlGo'
  where
    scanlGo'           :: (b -> a -> b) -> b -> [a] -> [b]
    scanlGo' f !q ls    = q : (case ls of
                            []   -> []
                            x:xs -> scanlGo' f (f q x) xs)

