6723: 小Z的关系距离

小 Z 学习了辩证唯物主义，知道了联系具有普遍性。他看着草稿纸上的字符串，就想挖掘它们之间的关系。小 Z 认为，对于两个字符串 $a,b$，如果它们各自删除不超过其自身长度一半的字符能够相等，则称 $a,b$ 有距离为 $1$ 的关系。而如果存在另一个字符串 $c$，它和 $a$ 有距离为 $1$ 的关系，和 $b$ 有距离为 $n$ 的关系，则称 $a,b$ 有距离为 $n + 1$ 的关系。现在小 Z 随机挑选出了两个小写字母字符串 $a,b$，想知道它们之间关系的最小距离，希望你帮帮他。

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