import           Control.Applicative
import           Control.Monad
import qualified Data.ByteString.Char8 as B

import           Data.Array.IArray

solve :: IO ()
solve = do
    xs <- B.getLine
    ys <- B.getLine
    print $ lcs xs ys

lcs :: B.ByteString -> B.ByteString -> Int
lcs xs ys = go (lx, ly)
  where
    lx = B.length xs - 1
    ly = B.length ys - 1

    m :: Array (Int, Int) Int
    m = listArray ((-1, -1), (lx, ly))
      $ fmap go [(i, j) | i <- [-1 .. lx], j <- [-1 .. ly]]

    go (i, j)
        | i < 0 || j < 0 = 0
        | x == y         = 1 + m ! (i - 1, j - 1)
        | x /= y         = max (m ! (i, j - 1)) (m ! (i - 1, j))
      where
        x = xs `B.index` i
        y = ys `B.index` j

main :: IO ()
main = do
    n <- readLn
    replicateM_ n solve

