import scala.io.StdIn.{readInt,readLine}
import scala.collection.mutable.ArrayBuffer

object Main {
  def max(x:Int,y:Int) = if(x>y) x else y

  def main(args:Array[String]) = {
    val n = readInt
    val b = new ArrayBuffer[Int]

    for(i<-0 until n) {
      val s1 = ' ' + readLine
      val s2 = ' ' + readLine
      val N = s1.length
      val M = s2.length

      val a = Array.ofDim[Int](N,M)
      for(i<-1 until N)
        for(j<-1 until M)
          if(s1(i)==s2(j)) a(i)(j) = a(i-1)(j-1)+1 else a(i)(j) = max(a(i-1)(j), a(i)(j-1))
      b += a(N-1)(M-1)
    }
    println(b.mkString("\n"))
  }
}