问题描述

在百人一首中，有两首以「わたのはら」开头的歌，通过听第6个字就能确定是哪首歌。也就是说，对于满足「从开头到第$q$个字与其他百人一首的任何一首歌都不相同」条件的最小$q$是$p$，那么这首歌就称为「$p$字决定」。例如，以「わたのはら」开头的两首歌是$6$字决定。

数学家高桥君扩展了$p$字决定的概念，引入了真正的$p$字决定。某首歌$S$被称为真正的$p$字决定，当且仅当满足以下条件的最小$q$是$p$：

• $S$的任何长度为$q$的子序列都不是其他歌集中的任何歌曲的子序列。

高桥君立刻想要使用真正的$p$字决定，于是他决定在青木的歌集「一人二首」中尝试。青木的歌集只包含由两首歌$S$和$T$组成。请代表高桥君求和歌$S$在「一人二首」中的真正的$p$值。保证这两首歌是不同的。

子序列定义：

一个字符串$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

abbcd
abccd```

### 输出样例 1

```plain
5```

---

### 输入样例 2

```plain
watanoharayasosimakaketekogiidenuto
watanoharakogiidetemirebahisakatano```

### 输出样例 2

```plain
20```

---

### 解释

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