题目描述

小 Z 学习了辩证唯物主义，知道了联系具有普遍性。他看着草稿纸上的字符串，就想挖掘它们之间的关系。

小 Z 认为，对于两个字符串 $a,b$，如果它们各自删除不超过其自身长度一半的字符能够相等，则称 $a,b$ 有距离为 $1$ 的关系。而如果存在另一个字符串 $c$，它和 $a$ 有距离为 $1$ 的关系，和 $b$ 有距离为 $n$ 的关系，则称 $a,b$ 有距离为 $n + 1$ 的关系。

现在小 Z 随机挑选出了两个小写字母字符串 $a,b$，想知道它们之间关系的最小距离，希望你帮帮他。

输入格式

第一行包含一个字符串 $a$。

第二行包含一个字符串 $b$。

输出格式

第一行包含一个整数，表示 $a,b$ 之间关系的最小距离。

abcdef
axcyd

1

a
b

2

abb
baa

2

提示

对于 $30\%$ 的数据，$a,b$ 由同一字母构成。

对于 $100\%$ 的数据，$1 \leq |a|,|b| \leq 100$。