T <- scan(file = "stdin", n = 1)

for (t in 1:T) {
  # Read in the strings A, B, and Q
  input <- scan(file = "stdin", n = 3, what = character())
  A <- strsplit(input[1], "")[[1]]
  B <- strsplit(input[2], "")[[1]]
  Q <- as.integer(input[3])

  results <- numeric(Q)


  for (q in 1:Q) {
    # Read in prefix size P and suffix size S
    input <- scan(file = "stdin", n = 2)
    P <- input[1]
    S <- input[2]

    A_prefix <- A[1:P]
    B_suffix <- B[(length(B) - S + 1):length(B)]

    max_match <- 0
    for (i in 1:P) {
      if (startsWith(B_suffix, A_prefix[i:P])) {
        max_match <- max(max_match, P - i + 1)
      }
    }

    results[q] <- max_match
  }

  cat(sprintf("Case #%d:", t))
  cat(sprintf(" %d", results))
  cat("\n")
}