import scala.util.parsing.combinator.RegexParsers

object Solution {  
  val in = {
    val lines = scala.io.Source.stdin.getLines()
    lines map (_ split ' ' filter (_.nonEmpty)) flatten
  }
  
  def nextInt() = in.next().toInt
  
  def main(args: Array[String]): Unit = {    
    val testCount = nextInt()
    for (test <- 1 to testCount) {
      val L = nextInt()
      val regex = in.next()
      val r = DamnParser(regex).get


      // println(r)

      val ans = L to (500 min (L + regex.length + 1)) find (r.matchLen(_))
      println(ans.getOrElse(-1))
    }
  }
}

abstract class RegExpr {
  val memo = scala.collection.mutable.Map[Int, Boolean]()
  def matchLen(n: Int): Boolean  
}
case class Literal(s: String) extends RegExpr {
  override def matchLen(n: Int): Boolean = {
    s.length == n
  }


  override def toString = s
}
case class Cat(first: RegExpr, second: RegExpr) extends RegExpr {

  override def matchLen(n: Int): Boolean = {
    if (!memo.contains(n))
      memo(n) = (0 to n).exists{ k =>
        first.matchLen(k) && second.matchLen(n - k)
      }

    memo(n)
  }


  override def toString = s"$first$second"

}
case class Or(first: RegExpr, second: RegExpr) extends RegExpr {

  override def matchLen(n: Int): Boolean = {
    if (!memo.contains(n))
      memo(n) = first.matchLen(n) || second.matchLen(n)
    memo(n)
  }

  override def toString = s"($first|$second)"

}
case class Star(r: RegExpr) extends RegExpr {
  override def matchLen(n: Int): Boolean = {
    if (!memo.contains(n))
      memo(n) = (n == 0) || r.matchLen(n) || {
        (1 until n).exists(k => r.matchLen(k) && matchLen(n - k))
      }
    memo(n)
  }

  override def toString = s"($r)*"
}

object DamnParser extends RegexParsers {
  def base: Parser[RegExpr] =
    "[a-z]".r ^^ (Literal(_)) |
    "(" ~> regex <~ ")"

  def factor: Parser[RegExpr] =
    (base ~ rep("*")) ^^ { case (b ~ list) => if (list.isEmpty) b else Star(b) }

  def term: Parser[RegExpr] =
    (factor ~ rep(factor)) ^^ {case (seed ~ list) => list.foldLeft(seed) {
        case (acc, f) => Cat(acc, f)
      }
  }

  def regex: Parser[RegExpr] =
      repsep(term, "|") ^^ { case list => list.reduce((a,b) => Or(a, b)) }

  def apply(input: String): Option[RegExpr] = parseAll(regex, input) match {
    case Success(result, _) => Some(result)
    case NoSuccess(_, _) => None
  }
}