import scala.io.StdIn.{readInt,readLine}
  
object Main {
  def max(x:Int,y:Int) = if(x>y) x else y
  def main(args:Array[String]) = {
    val n = readInt

    for(i<-0 until n) {
      val s1 = readLine.trim
      val s2 = readLine.trim
      val maxN = s1.length
      val maxM = s2.length

      val a = Array.ofDim[Int](maxN,maxM)
      for(i<-0 until maxN) if(s1(i)==s2(0)) a(i)(0) = 1
      for(j<-0 until maxM) if(s1(0)==s2(j)) a(0)(j) = 1
      for(i<-1 until maxN) {
        for(j<-1 until maxM) {
          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))
          }
        }
      }
      println(a(maxN-1)(maxM-1))
    }
  }
}