You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

塔子哥是学校舞台的灯光师，舞台灯有十六种不同的颜色和光效组合，对应十六进制的每个数{0，1，2，3，4，5，6，7，8，9，A，B，C，D，E，F}。

即将举办的毕业晚会策划把舞台灯光的要求发到了塔子哥这里，但是舞台的灯光不能直接从外部输入，需要用特定方式调整：舞台灯用一个十六进制数串表示，每次可以选择数串中的某个子串，进行一次整体变大或变小的翻转。

举个例子，假设数串"AABB"选择中间的子串"AB"，变大翻转会变成: "ABCB"，变小翻转会变成:"A9AB"。特别的，字符”0“变小的翻转会变成字符”F“，同理字符”F“的变大翻转会变成字符”0“，以此循环往复。

塔子哥想知道，给定两个数串 $s1$ 和 $s2$，最少可以用多少次翻转使得 $s1$ 变成 $s2$ 。

输入描述

输入第一行一个整数 $T$ ，代表测试用例的组数。( $1 \leq T \leq 1000$)

接下来 $T$ 行，每一行两个数串 $s1$ 和 $s2$。（$s1$ 和 $s2$ 为十六进制数串，长度相等且小于等于4)

输出描述

输出 $T$ 行，每行一个整数，表示每组 $s1$ 翻转成 $s2$ 的最少步数。

样例

样例输入

5
AABB EEFF
FFF 999
01 AE
AFE B0F
ABCD EEEE

样例输出

4
6
6
1
4

思考

当$t = 1e5$ 时该如何做？