Problem: Maximum Matching

Input file: standard input Output file: standard output Time limit: 2 seconds Memory limit: 256 megabytes

Today you will be going skiing on a piste consisting of $n$ segments, where you travel in order from segment $1$ to $2$ ... to $n$. In each segment, you can perform one ski trick represented by a lowercase letter a through z. You don't have to perform the trick if you don't want to.

There is a Skiing Contest for Computer science (SCCs) where contestants attempt do tricks in a way that they are accepted by a regular expression.

The regular expression consists of $m$ characters with the following properties.

• Each expression consists of the lowercase letters a through z and the characters ?, *, [, ], (, )

• Each letter matches a trick corresponding to that letter.

• The question mark ? matches any trick.

• The brackets [ and ] are always correctly paired. Inside them are only lowercase letters. A pair of brackets and the letters inside match any single trick that matches any letter in side the brackets.

• The asterisk * indicates that the preceding sequence -- a letter, a question mark, brackets [], or a portion of the expression enclosed in parentheses () -- may be repeatedly matched any amount of times. The number of repetitions may be zero.

• Parentheses ( and ) are always correctly paired, and are always immediately followed by an asterisk. Inside the parentheses, there is an expression with the same properties listed above, but does not contain parentheses.

A routine is a sequence of tricks that can be performed while traveling through the piste.

A matching routine is a routine whose sequence of tricks matches the regular expression.

A maximum matching routine is a matching routine such that there are no matching routines with more tricks.

How many tricks are in a maximum matching routine? If no matching routines exist, print -1.

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1≤t≤1000$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($1≤n≤1000$) -- the number of segments.

The second line of each test case contains a string $s$ ($|s|=n$) -- the trick you can perform for each segment.

The third line of each test case contains an integer $m$ ($1\le m\le 1000$) -- the length of the regular expression for matching.

The fourth line of each test case contains a string $p$ ($|p|=m$) -- the regular expression for matching.

For each test case, output the number of tricks in the maximum matching routine, or -1 if no matching routine exists.

input:

4
3
aba
2
a*
9
algorithm
6
design
4
food
13
([ba]g??t*e)*
20
candycandycandycandy
14
[abc]*(andy)*?

output:

2
-1
0
14