import scala.io.StdIn

object Main {
  def func(prev: List[Int], input: (String, Char)): List[Int] =
    if(prev.length <= 1 || input._1.isEmpty) List(0)
    else {
      val next = func(prev.tail, (input._1.tail, input._2))
      if(input._1.head == input._2) (prev(1)+1) :: next
      else Math.max(next.head, prev.head) :: next
    }

  def solve(input: (String, String)): Int =
    input._2.foldLeft(List.fill(input._1.length+1)(0)){
      (prevList, ch) => func(prevList, (input._1.reverse, ch))
    }.head
  
  def main(args: Array[String]) {
    val n = StdIn.readInt()
    List.fill(n)((StdIn.readLine(), StdIn.readLine())).map(solve).foreach(println)
  }
}