The 5th test case in the official data violated the constraint that the regular expression length must not exceed 50, so the data for the 5th test case has been modified.

When developing a Web backend, a very important component is the router. Generally, backend code consists of many actions, and the role of the router is to map incoming requests to the corresponding action based on the URL.

When a request reaches the backend Web server, there is no need to consider the domain name or port, so a request has the following form:

"/{something_1}/{something_2}/.../{something_k}" or "/{something_1}/{something_2}/.../{something_k}?{parameter_list}"

where the parameter_list is composed of: "{name_1}={value_1}&{name_2}={value_2}&...&{name_n}={value_n}". (In the first case, the parameter_list is empty.)

For example, "/user/list/show?gender=male&birthyear=1990" is a valid request, which contains two parameters, gender and birthyear, with the corresponding values male and 1990.

A router consists of many paths, and each path corresponds to an action. When the router matches a URL to a path, it only looks at the part before the parameter_list; for example, the previous request only looks at the "/user/list/show" part. The parameters within the parameter_list are sent directly to the action. Therefore, a path always has the following form:

"/{something_1}/{something_2}/.../{something_k}"

To make the router more flexible, each segment something can be a specific string or a regular expression to match and extract the content of that part as a parameter to be sent to the action. In this case, the content of something is ":{regexp_name}", where regexp_name corresponds to a regular expression, which will be provided later. For example, a path in the router is "/user/:handle/show", where ":handle" corresponds to a regular expression, assuming it can match all non-empty strings consisting of lowercase English letters. In this case, the request "/user/testuser/show" can match this path, and an additional parameter with name handle and value testuser is sent to the action. Furthermore, if the request is "/user/testuser/show?avatar=true&message=hello", it not only matches the previous path, but the parameters sent to the action will be three: handle, avatar, and message, with corresponding values testuser, true, and hello.

However, using paths with regular expressions is subject to some restrictions. Specifically, if there are two paths in the router whose first $i$ something segments are identical (these $i$ segments may contain regular expression items, in which case the regular expressions must have the same name), and the $(i+1)$-th something segment is different, then there are two cases:

1. If one path's segment is a plain string and the other path's segment corresponds to a regular expression, then this regular expression must not be able to match the string in the $(i+1)$-th segment of the first path. For example, if one path is "/foo/:tmp/bar/pop" and another path is "/foo/:tmp/:exp/push", then the regular expression corresponding to exp must not match bar.
2. If both paths' segments are regular expressions, then the strings matched by these two regular expressions must have no intersection. For example, if one path is "/foo/:tmp/:aaa/push" and another path is "/foo/:tmp/:bbb/pop", then there is no string that can be matched by both the regular expression corresponding to aaa and the regular expression corresponding to bbb.

Finally, let's introduce the regular expressions. To simplify the situation, the regular expression rules in this problem are simplified compared to those used in practice. The grammar of regular expressions includes the concepts of Atom, Quantifier, Term, and Alternative. Using Regexp to represent a regular expression, each concept is defined as follows:

1. A Regexp can consist of a single Alternative, or an Alternative and a Regexp connected by the character "|". In the former case, the regular expression matches everything that the Alternative can match. In the latter case, for a string to be matched by the regular expression, it must be matched by the Alternative before the "|" or by the Regexp after the "|".
2. An Alternative consists of a single Term or multiple Terms connected, and it matches the concatenation of strings matched by these Terms. In other words, for a string to be matched by this Alternative, the string must be splittable into several segments (the number of segments is equal to the number of Terms in the Alternative), and each segment must be matched by the corresponding Term in the Alternative in order.
3. A Term consists of an Atom or an Atom with a Quantifier. As will be learned later, a Quantifier corresponds to an interval of allowed repetition counts. If a Term consists of a single Atom, the content the Term can match is the same as the Atom. If an Atom is followed by a Quantifier, then if a string can be divided into several segments (the number of segments is within the interval specified by the Quantifier) such that each segment can be matched by the Atom, then the string can be matched by this Term.
4. A Quantifier has the form "{lower_bound,upper_bound}", where lower_bound and upper_bound each correspond to a non-negative integer not exceeding $20$, and $\text{upper_bound} \geq \text{lower_bound}$. The interval corresponding to the Quantifier is the closed interval $[\text{lower_bound}, \text{upper_bound}]$. Note that upper_bound can be empty (the comma in the middle remains), and an empty upper_bound means the upper bound is infinity. "{1,3}", "{0,1}", "{2,2}", and "{3,}" are all valid Quantifiers, but "{3,2}" and "{,1}" are invalid.
5. An Atom has three forms: The first is a single character, where the character is restricted to English letters (including uppercase and lowercase) and digits. In this form, the content the Atom can match is that character. The second form is a character range, specifically "[lower-upper]", where lower and upper are single characters, satisfying that they are either both lowercase English letters, both uppercase letters, or both digits, and the ASCII code of lower is not greater than the ASCII code of upper. In this case, the content the Atom can match is any character within this range (including lower and upper). The third form is "(Regexp)", which is a valid regular expression enclosed in parentheses. In this case, the content the Atom can match is the same as the regular expression inside the parentheses.

According to the above grammar, "[0-9]{1,3}" is a valid regular expression, which can match strings of length $1 \sim 3$ consisting of digits. "([a-z]|[0-9]){3,10}" is also a valid regular expression, which can match strings of length $3 \sim 10$ consisting of lowercase English letters and digits. A more complex example is "01[0-1]{0,}|10[0-1]{0,}", which can match all strings starting with 01 or 10.

Input

The first line contains a positive integer $T$, representing the number of test cases. The data for each test case is given below.

The first line of each test case contains a positive integer $N$, representing that there are $N$ paths in the router. The next $2N$ lines describe each path, with every two lines describing one path. The first line is the URL matched by the path, in the form:

"/{something_1}/{something_2}/.../{something_k}"

Each something segment is either a specific string (consisting of uppercase English letters, lowercase English letters, and digits, with length in $[1,50]$) or ":{regexp_name}", where regexp_name consists of uppercase and lowercase English letters with length not exceeding $30$. The specific regular expressions will be given in the subsequent input. The second line describing the path is the corresponding action name (consisting of uppercase and lowercase English letters, with length in $[1,30]$).

The following several lines describe all regular expressions appearing in the previous paths. Each line describes one regular expression and contains two non-empty strings (separated by a space). The preceding string represents the regexp_name, and the following string represents the corresponding regular expression (length not exceeding $50$). Note that the same regexp_name may appear multiple times in the previous paths (multiple times in one path or in different paths). In this case, the regular expressions they correspond to are identical, and they will only be described once in the input. The data also guarantees that the regexp_names given here have appeared in at least one path.

The next line contains a positive integer $M$, representing that there are $M$ requests sent. The next $M$ lines each describe the URL of a request. The URL is in the form of "/{something_1}/{something_2}/.../{something_k}" or "/{something_1}/{something_2}/.../{something_k}?{name_1}={value_1}&{name_2}={value_2}&...&{name_n}={value_n}", where all something and value consist of uppercase English letters, lowercase English letters, and digits with length in $[1,50]$, and all name consist of uppercase and lowercase English letters with length in $[1,30]$.

Output

For each test case, first output "Case #{case_no}:" on a separate line, where case_no represents the current test case number (starting from $1$).

Each subsequent line corresponds to each request. If no path can match the request's URL, output "404 Not Found".

If a path can match the request, output "Request matches action "{action_name}" with parameters {parameter_list}", where action_name is the name of the action corresponding to the matched path, and parameter_list is all the parameters.

• The parameter_list is output as a dictionary. For example, if there are three parameters with names avatar, message, and page, and corresponding values true, hello, and 2, then the output parameter_list is "{"avatar":"true","message":"hello","page":"2"}" (all parameters are sorted by name in lexicographical order).
• Note that in a request, parameters with the same name may appear multiple times. For example, if the request URL is "/user/me/show?name=you&name=he" and the matched path is "/user/:name/show", then the parameter_list is "{"name":["me","you","he"]}". The values inside the square brackets are given in the order they appeared in the request URL.
• Please refer to the examples for more specific details. The data guarantees that a request will not be matched by multiple paths.

Examples

Input 1

3
3
/user/:id/show
userShow
/message/list
messageList
/message/:id/show
messageShow
id [0-9]{2,4}
3
/message/list
/user/123/show?avatar=true
/message/5312/show?page=1
1
/foo/:id/:bar/:bar
fun
id [0-9]{2,4}
bar [a-z]{1,3}
1
/foo/777/az/bc?bar=xyz&bar=zzz
2
/user/:handle/show
userShow
/user/:id/show
userShow
id [0-9]{2,4}
handle ([a-z]|[A-Z])([a-z]|[A-Z]|[0-9]){4,10}
4
/user/259/show
/user/wjmzbmr/show?like=true
/user/0xxx/show
/user/WJMZBMR/show?love=true

Output 1

Case #1:
Request matches action "messageList" with parameters {}
Request matches action "userShow" with parameters {"avatar":"true","id":"123"}
Request matches action "messageShow" with parameters {"id":"5312","page":"1"}
Case #2:
Request matches action "fun" with parameters {"bar":["az","bc","xyz","zzz"],"id":"777"}
Case #3:
Request matches action "userShow" with parameters {"id":"259"}
Request matches action "userShow" with parameters {"handle":"wjmzbmr","like":"true"}
404 Not Found
Request matches action "userShow" with parameters {"handle":"WJMZBMR","love":"true"}

Constraints

For 30% of the data, no regular expressions will appear in the paths;

For 100% of the data, $N, M \leq 20000$, $T \leq 5$, and the input file size does not exceed $10\texttt{MB}$. There are at most $50$ regular expressions with different names.

Note: The data for this problem is well-constructed.