問題文

百人一首には「わたのはら」で始まる歌が$2$首あり、$6$文字目を聞いて初めて取る札を確定できます。このように、「最初から $q$ 文字目までが百人一首の他のどの歌とも共通しない」を満たす最小の $q$ が $p$ であるとき、その歌は「 $p$ 字決まりである」と言います。例えば、「わたのはら」で始まる$2$首は$6$字決まりです。

数学家の高橋くんは、 $p$ 字決まりの概念を拡張した真・ $p$ 字決まりを考えました。ある歌 $S$ が真・ $p$ 字決まりであるとは、以下の条件を満たす最小の $q$ が $p$ であることを指します。

• $S$ のどの長さ $q$ の部分列も、歌集の他の歌の部分列でない

この真・ $p$ 字決まりをさっそく使いたくなった高橋君は、青木さんの歌集「一人二首」の歌で調べることにしました。一人二首は、青木さんの詠んだ$2$つの歌 $S,\\ T$ のみで構成されています。高橋くんに代わって、和歌 $S$ が「一人二首」において真・何字決まりであるか求めなさい。$2$つの和歌は同一ではないことが保証されます。

部分列とは

ある文字列 $s$ の部分列は、 $s$ の中から連続するとは限らない$0$個以上の文字を選択して元の順に並べた文字列のことを指します。例えば、rhhanやirohachan、空文字列はirohachanの部分列ですが、takahashikunやnahcahoriはそうではありません。

制約

• $S$ と $T$ は英小文字のみで構成される文字列
• $1 \\leq |S|=|T| \\leq 5000$
• $S \\neq T$

入力

入力は以下の形式で標準入力から与えられる。

$S$ $T$

出力

和歌 $S$ が真・$p$ 字決まりであるとき、$p$ を$1$行で出力せよ。

入力例 1

abbcd
abccd```

### 出力例 1

```plain
5```

* * *

### 入力例 2

```plain
watanoharayasosimakaketekogiidenuto
watanoharakogiidetemirebahisakatano```

### 出力例 2

```plain
20```

* * *

### 解説

[解説](https://img.atcoder.jp/iroha2019-day2/editorial-A.pdf)