小 Z 学习了辩证唯物主义，知道了联系具有普遍性。他看着草稿纸上的字符串，就想挖掘它们之间的关系。
小 Z 认为，对于两个字符串 ，如果它们各自删除不超过其自身长度一半的字符能够相等，则称 有距离为 的关系。而如果存在另一个字符串 ，它和 有距离为 的关系，和 有距离为 的关系，则称 有距离为 的关系。
现在小 Z 随机挑选出了两个小写字母字符串 ，想知道它们之间关系的最小距离，希望你帮帮他。
第一行包含一个字符串 。
第二行包含一个字符串 。
第一行包含一个整数，表示 之间关系的最小距离。
abcdef axcyd
1
a b
2
abb baa
对于 的数据， 由同一字母构成。
对于 的数据，。
