問題文

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

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

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

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

制約

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

入力例 1

abbcd
abccd

出力例 1

5

入力例 2

watanoharayasosimakaketekogiidenuto
watanoharakogiidetemirebahisakatano

出力例 2

20

解説