题单赞助商

题目背景

乐柠兔正在整理一份题单，她发现两个编号 $a$ 和 $b$ 之间，有一种“相似度”可以用来衡量：把它们写成十进制后，统计有多少个位置上的数字完全相同。

为了挑选一个最合适的题号，她需要在一个区间内找到一个编号 $x$，使得它同时“尽量不像”左端点 $l$，也“尽量不像”右端点 $r$。

对两个整数 $a$ 与 $b$，定义函数 $f(a,b)$：

• 将 $a$ 与 $b$ 写成十进制表示（不允许有前导零）；
• 从最高位到最低位逐位比较；
• $f(a,b)$ 等于数字相同的位置数量。

例如：

• $f(12,21)=0$
• $f(31,37)=1$
• $f(19891,18981)=2$
• $f(54321,24361)=3$

现在给定两个十进制长度相同的整数 $l$ 和 $r$。

请你在所有满足 $l \le x \le r$ 的整数 $x$ 中，求出下面表达式的最小值： $f(l,x) + f(x,r)$

输入格式

本题包含多组测试数据。

• 第一行输入一个整数 $t$，表示测试数据组数。
• 接下来 $t$ 行，每行输入两个整数 $l$ 和 $r$。

输出格式

对于每组测试数据：

• 输出一行一个整数，表示在所有 $l \le x \le r$ 中$f(l,x)+f(x,r)$ 的最小值。

样例

样例输入

14
1 1
2 3
4 6
15 16
17 19
199 201
899 999
1990 2001
6309 6409
12345 12501
19987 20093
746814 747932
900990999 900991010
999999999 999999999

样例输出

2
1
0
3
2
2
1
3
3
4
3
5
12
18

样例解释

• 第 1 组：取 $x=1$ ，$f(1,1)+f(1,1)=1+1=2$
• 第 2 组：取 $x=2$，$f(2,2)+f(2,3)=1+0=1$

数据范围与约定

对于 100% 的数据，保证：

• $1 \le t \le 10^4$
• $1 \le l \le r < 10^9$
• $l$ 与 $r$ 的十进制表示长度相同
• $l$ 与 $r$ 均不存在前导零