题目描述

小蓝最近迷上了全排列，现在他有一个长度为 $17$ 的排列，里面包含的元素有： abcdefghijklnopqr，即 a 至 r 中除了 m 以外的所有小写字母，这 $17$ 个字母在任何一个排列中都恰好出现一次。前面几个排列依次是：

第 1 个排列为：abcdefghijklnopqr；
第 2 个排列为：abcdefghijklnoprq；
第 3 个排列为：abcdefghijklnoqpr；
第 4 个排列为：abcdefghijklnoqrp；
第 5 个排列为：abcdefghijklnorpq；
第 6 个排列为：abcdefghijklnorqp；
第 7 个排列为：abcdefghijklnpoqr；
第 8 个排列为：abcdefghijklnporq；
第 9 个排列为：abcdefghijklnpqor；
第 10 个排列为：abcdefghijklnpqro。

对于一个排列，有两种转移操作：

• 1）转移到其下一个排列。如果当前排列已经是最后一个排列，那么下一个排列就是第一个排列。
• 2）转移到其上一个排列。如果当前排列是第一个排列，那么上一个排列就是最后一个排列。

本题进行扩展，小蓝现在有两个长度为 $N$ 的排列，分别为排列 $A$，以及排列 $B$，他现在想知道，在只有上述两种转移操作的前提下，排列 $A$ 最少转移多少次能得到排列 $B$。

输入描述

第一行包一个整数 $T$，表示测试数据的规模。

接下来 $T$ 行每行 $2$ 个字符串 $S_1,S_2$。

输出描述

对每个输入输出一个整数表示答案。

1
aejcldbhpiogfqnkr ncfjboqiealhkrpgd

106148357572143

评测用例规模与约定：

对于所有评测用例，$1≤T≤10$ ，$1≤N≤20$，两个字符串包含的字符一样，且内部不重复。