天作之合

生活就是一次A\*，你是我的第一个目标状态。——小明

在小明的学校中，一共有若干个女生。小明认为每个女生的特征可以抽象为一个6位的数字串其中不重复地包含1~6这6个数码。 在小明心中，有一个理想的女生，她的特征数字串为A。如果串Y是串X交换两个连续的数码所得，那么我们认为特征数字串X和Y相似。首先，小明找到了他的同桌，她的特征数字串为S。每次，小明会寻找一个特征数字串和当前串相似的女生，直到寻找到适合他的（即特征数字串和A相同或相似的）。定义每个女生的合适程度为找到此人至少需要找女生的数量（包括他的同桌和此人自己）。显然，合适程度数值越小的女生越适合小明。 然而，小明觉得老天不会轻易地让他找到，所以他认为合适程度第二小的才是他最合适的伴侣（也就是小红）。那么，请你帮他写一个程序，求出对于小明，小红的合适程度是多少。

第1行，一个特征数字串A。 第2行，一个特征数字串S。

一行，一个正整数表示小红的合适程度。

123654
123456

3

对于全部数据，保证串A和S合法，且保证能找到。 数据比较弱。