Solution.scala

object Solution extends App {

  @inline def diff(str1: String, str2: String, i: Int, j: Int, count: Int, maxCalced: Int): Int = {
    var c = count
    var a = 0

    val maxCount = str1.size - Math.max(i, j)

    if (maxCount <= maxCalced)
      return 0

    var d = 0

    while (d < maxCount) {
      if (str1(d + i) == str2(d + j))
        a += 1
      else {
        c -= 1
        if (c == -1) {
          return a
        }
        else a += 1
      }
      d += 1
    }
    a
  }

  def process(str1: String, str2: String, count: Int): Int = {
    var max = Math.min(str1.size, count)
    var i = 0
    var j = 0

    while (j < str2.size - max) {
      max = Math.max(max, diff(str1, str2, i, j, count, max))
      i += 1
      if (i >= str1.size - max) {
        j += 1
        i = 0
      }
    }

    max
  }


  Range(0, readInt()).foreach { _ =>
    val Array(ss, p, q) = readLine().split(" ")
    val s = ss.toInt

    println(process(p, q, s))
  }
}