Problem Statement

You are given strings $A$, $B$, each of which is a regular expression (of a restricted form) consisting of ?, *, and lowercase letters.
Here, ? denotes zero or one repetition of the preceding character, and * denotes zero or more repetitions of the preceding character.
For $A$, $B$, let $G_A$, $G_B$ respectively be the set of strings generated by the regular expression.
For example, when $A = $ "a?b*", we have $G_A=\{$"", "a", "b", "ab", "bb", "abb", "bbb", "abbb", $\cdots \}$.

For strings $a$ and $b$ consisting only of lowercase letters, the edit distance $d(a, b)$ between $a$ and $b$ is defined as
"the minimum number of steps required to transform $a$ into $b$ by single-character insertions, deletions, and substitutions"
.
For example, consider the edit distance between "abcdefgh" and "zcdefgha". For "abcdefgh",
deleting a, replacing b with z, and adding a transforms it into "zcdefgha",
and since this is the minimum number of steps, we have $d("$abcdefgh$", "$zcdefgha$") = 3$.

The distance between regular expressions $D(A, B)$ for $A$, $B$ is defined as $\min_{(a, b) \in G_A \times G_B } d(a, b)$.
In other words, $D(A, B)$ is defined as "the minimum edit distance over all combinations of strings that can be generated by A and B, respectively".
Find $D(A, B)$.

Input

$A$
$B$

$A$, $B$ are strings consisting of ?, *, and lowercase letters.
? and * do not appear consecutively in $A$ or $B$ (they do not contain "??", "?*", "*?", or "**" as a substring).
The first character of $A$, $B$ is neither ? nor *.
$1 \leq |A| \leq 2000$
$1 \leq |B| \leq 2000$

Output

Print $D(A, B)$ on one line.
Print a newline at the end.

Sample

ab?c
abc

0

a*bcd
aaaabd?

1

aaaaabbbaaaaa
a*b?c*

3

aaaaabbbaaaaa
a*b?a*

2