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 } }