object Main extends App {
  val q: Int = io.StdIn.readInt()
  (for (_ <- 0 until q) yield {
    val a: String = io.StdIn.readLine()
    val b: String = io.StdIn.readLine()
    val n: Int = a.length
    val m: Int = b.length
    val cache: Array[Array[Int]] = Array.ofDim(n+1, m+1)
    for (i <- 1 to n)
      for (j <- 1 to m)
        cache(i)(j) =
          if (a(i-1) == b(j-1)) cache(i-1)(j-1) + 1
          else cache(i)(j - 1).max(cache(i-1)(j))
    cache(n)(m)
  }) foreach println
}
