Regular expressions (abbreviated regex or regexp) are patterns which are used to represent a set of strings. A regex can be represented as a graph with multiple nodes. One of them is the start node and another one is the final node, and characters of regex can serve as edges.

Formally, a regex and the matching string abides by the following rules.

  • Epsilon (): is used to represent a regular expression that matches an empty string. A string matches when "".

Epsilon

  • Literal character: A single character, , is a regular expression. Any string where will match it. For this problem, will a lowercase latin letter .

Literal

  • Concatenation: If and are regular expressions then is also a regular expression. A string matches if there exists two substrings and where and matches , and matches .

Concatenation

  • Alternation (): If and are regular expressions then is also a regular expression. Any string which matches or will match .

alternation

  • Kleene Star (): If is a regular expression then is also a regular expression. A string matches it if can be partitioned into zero or more substrings such that and each matches .

Kleene

  • Precedence Order: Kleene Star > Concatenation > Alternation

Sample Regex
Below is the graph for regex ((ab|ba)*)

Problem Statment
You are given a regex, , and an integer, . Find the length of the smallest string whose length is equal to or greater than , but not greater than , and matches regex .

Input Format

The first line of input contains an integer, , representing the number of test cases. Each test case consists of two lines. The first line will contain a non-negative integer representing the minimum length of the string to be searched, . The next line will contain a valid regular expression, .

Constraints

  • will be a valid regular expression
  • will consist of a lowercase latin character or any of { '(', ')', '*' , '|' }

Output Format

For each case, print the length of the smallest string matching regex and whose length is equal to or greater than , but not greater than . If no such string is possible, print "-1" (without quotes).

Sample Input

3
5
ab*(c|d)
5
aba
7
(ab|ba)*

Sample Output

5
-1
8

Explanation

  • Test Case #00
    "ab*(c|d)" represents the set of strings where the first character is 'a', last character is either 'c' or 'd'. In between them there can be zero or more occurrences of 'b'. As we have to create a string of minimum length , we will add three 'b' in between them. Two possible solutions, with minimum length, are "abbbc" and "abbbd".

  • Test Case #01
    Since no string is possible of minimum length and matching regex "aba", we will print here.

  • Test Case #02
    "(ab|ba)*" represents an set of strings which is a concatenation of 0 or more "ab"/"ba". It will always be of even length.

  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score