Eileen 每次在 A-SOUL 出去演出时，都会在行李箱里装很多东西。然而，如果行李箱里的东西太多，行李箱上的 4 位密码锁就会变得很难转动。

锁的状态由锁上的四个数字组成。在一步操作中，她可以选择连续的数字同时向上转动 1 位或同时向下转动 1 位。例如，她可以在一步内将 0000 转动为 0111 或 0900，因为转动的数字是连续的；但她不能在一步内将 0000 转动为 0101。由于她力气很小，她希望转动锁的次数尽可能少。

现在锁处于状态 $a_0a_1a_2a_3$，密码是 $b_0b_1b_2b_3$。作为 A-SOUL 的粉丝，请你帮助 Eileen 找到解锁的最优方案，但你只需要告诉 Eileen 她最少需要转动多少次。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

每个测试用例包含一行，包含初始状态 $a_0a_1a_2a_3$ 和目标状态 $b_0b_1b_2b_3$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示解锁所需的最少步数。

样例

输入 1

6
1234 2345
1234 0123
1234 2267
1234 3401
1234 1344
1234 2468

输出 1

1
1
4
5
1
4