let lcs x y =
  let m = String.length x in
  let n = String.length y in
  let dp = Array.make ((m+1)*(n+1)) 0 in
  let rec duduwa i j =
    if j > n then doit (i + 1)
    else begin
      dp.(i*(n+1)+j) <- if x.[i-1] = y.[j-1] then dp.((i-1)*(n+1)+j-1) + 1 else if dp.((i-1)*(n+1)+j) > dp.(i*(n+1)+j-1) then dp.((i-1)*(n+1)+j) else dp.(i*(n+1)+j-1);
      duduwa i (j + 1)
    end
  and doit i =
    if i > m then dp.(m*(n+1)+n)
    else duduwa i 1
  in
  doit 1

let () =
  let q = read_int () in
  let rec doit i =
    if i < q then begin
      let x = read_line () in
      let y = read_line () in
      Printf.printf "%d\n" (lcs x y);
      doit (i + 1)
    end
  in
  doit 0