Legend has it that the Old Gods' voices are dread whispers that no mere mortal can hope to resist. And now, the time of their awakening draws near. Will you head their whispers at your ear?

We may represent a whisper by a sequence of digits. And surprisingly, the whispers of the Old Gods can be characterized by a regular expression (<regex>). The syntax of a regular expression is shown below (in Backus-Naur form):

<regex> ::= <regex> <regex>
          | <regex> "|" <regex>
          | <regex> "+"
          | <atomic-regex>

<atomic-regex> ::= <digit>
                 | "[" <digit-sequence> "]"
                 | "(" <regex> ")"

where <digit> is any single digit (0, 1, ..., 9) and <digit-sequence> is any nonempty sequence of digits. In case of any ambiguity, the positive closure (<regex> "+") has the highest precedence, which is followed by the concatenation (<regex> <regex>), and the alternation (<regex> "|" <regex>) has the lowest precedence. For example, the regular expression 1|23+ should be parsed as (1|(2(3+))).

Every regular expression $$$R$$$ recognizes a set of digit strings, denoted $$$L(R)$$$, which is defined as follows:

• $$$L(R_1 R_2) = \{s \circ t | s \in L(R_1), t \in L(R_2) \}$$$, where $$$R_1$$$, $$$R_2$$$ are regular expressions and $$$\circ$$$ means string concatenation;
• $$$L(R_1 | R_2) = L(R_1) \cup L(R_2) $$$, where $$$R_1$$$, $$$R_2$$$ are regular expressions;
• $$$L(R +) = \bigcup_{i=1}^{\infty} \{s^i | s \in L(R) \}$$$, where $$$s^i = s \circ s^{i-1}$$$ $$$(i \gt 1)$$$ and $$$s^1 = s$$$;
• the regular expression $$$d$$$ (where $$$d$$$ is any single digit) recognizes the single digit $$$d$$$;
• the regular expression $$$[s]$$$ (where $$$s$$$ is any nonempty sequence of digits) recognizes any single digit appearing in $$$s$$$;
• parenthesizing a regular expression doesn't change the set it recognizes, i.e., $$$L((R)) = L(R)$$$.

Given a regular expression describing the whispers of the Old Gods and a whisper you heard last night, you wonder how close is the whisper you heard to the Old Gods'. Specifically, you want to know the minimum number of changes to make it recognized by the regular expression. There are three kinds of changes to the whisper:

• inserting a single digit at any position;
• removing any single digit;
• replacing any single digit with any other digit.

For example, let the regular expression be (5|6+)[12]3+, and the sequence of digits you've heard be 4334. One possible way to make minimum number of changes to make the digit sequence recognized by the regular expression is 4334 -> 54334 -> 52334 -> 5233.