module Main where

-- import Debug.Trace
import Data.List
import qualified Data.Sequence as S
import qualified Data.ByteString.Char8 as B
import Data.Int
import Data.Char
import Data.Array
-- import Data.Array.IO
import Data.Maybe
import qualified Data.Map as M
import Data.Ord
import Data.Functor
import Control.Applicative
import Control.Monad
import Text.Printf

solve :: [(String, String)] -> [Int]
solve [] = []
solve ((x, y):xs)
    | isShorter x y = (lcs x y):solve xs
    | otherwise = (lcs y x):solve xs

isShorter :: String -> String -> Bool
isShorter [] ys = True
isShorter xs [] = False
isShorter (x:xs) (y:ys) = isShorter xs ys 


lcs :: String -> String -> Int
lcs sX sY = iterY sY initialMemo where
    iterY [] m = last m
    iterY (y:ys) m = iterY ys (iterX sX m [0]) where
            iterX _ [a] ac = reverse ac
            iterX (x:xs) (a:nl@(b:ms)) ac@(c:cs) = setXY `seq` iterX xs nl (setXY:ac) where
                    setXY = if x == y then a + 1 else max b c
    initialMemo = replicate ((length sX)+1) 0

readIntLn:: IO Int
readIntLn = (fst . fromJust . B.readInt) <$> B.getLine

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

main :: IO() 
main = do
    n <- readIntLn
    l <- replicateM n read2Str
    mapM_  print $ solve l

