let lcs (x, y) =
  let s = String.length x in
  let t = String.length y in
  let dp = Array.make_matrix (s+1) (t+1) 0 in
  for i = 1 to s do
    for j = 1 to t do
      dp.(i).(j) <-
        if x.[i-1] = y.[j-1] then dp.(i-1).(j-1) + 1
        else max dp.(i-1).(j) dp.(i).(j-1)
    done
  done;
  dp.(s).(t)

let () =
  let n = read_int () in
  for _ = 0 to n - 1 do
    Scanf.scanf "%s %s\n" (fun x y -> (x, y))
    |> lcs
    |> Printf.printf "%d\n"
  done