問題文

? か * か 小文字のアルファベットからなる正規表現（のサブセット）の文字列 $A$, $B$ が与えられます。
ここで、? は1つ前の文字の0回もしくは1回の繰り返し、* は1つ前の文字の0回以上の繰り返しを表します。
$A$, $B$のそれぞれについて、その正規表現によって生成される文字列の集合を$G_A$, $G_B$とします。
例えば、$A = $ "a?b*"のとき、$G_A=\{$"", "a", "b", "ab", "bb", "abb", "bbb", "abbb", $\cdots \}$ です。

小文字アルファベットだけからなる文字列$a$と$b$について、$a$と$b$の 編集距離 $d(a, b)$を
「1文字の挿入・削除・置換によって、$a$を$b$に変形するのに必要な手順の最小回数」
と定めます。
例えば "abcdefgh"と"zcdefgha"の編集距離を考えると、 "abcdefgh" に対し、
aの削除、bのzへの置換、aの追加を行うことで "zcdefgha" に変形でき、
これが最小回数であるため、$d("$abcdefgh$", "$zcdefgha$") = 3$となります。

$A$、$B$に関する 正規表現間距離 $D(A, B)$ を $\min_{(a, b) \in G_A \times G_B } d(a, b)$ とします。
つまり、$D(A, B)$を「AとBそれぞれで生成されうる文字列の全ての組み合わせにおける編集距離の最小」と定義します。
このとき、$D(A, B)$ を求めてください。

入力

$A$
$B$

$A$, $B$ は ? か * か 小文字のアルファベットからなる文字列である。
? や * が$A$や$B$の中に連続して出現することはない ("??", "?*", "*?", "**"という文字列を連続部分文字列として含まない)。
$A$, $B$ の先頭文字が ? もしくは * であることはない。
$1 \leq |A| \leq 2000$
$1 \leq |B| \leq 2000$

出力

$D(A, B)$ を1行に出力してください。
最後に改行してください。

サンプル

ab?c
abc

0

a*bcd
aaaabd?

1

aaaaabbbaaaaa
a*b?c*

3

aaaaabbbaaaaa
a*b?a*

2