← 返回题目列表

Codeforces · 2121/E

E. 你的问题的赞助者

中文机器翻译题面 查看原题

对于两个整数 $$$a$$$ 和 $$$b$$$,我们将 $$$f(a, b)$$$ 定义为数字 $$$a$$$ 和 $$$b$$$ 的十进制表示中数字相同的位置数。例如,$$$f(12, 21) = 0$$$,$$$f(31, 37) = 1$$$,$$$f(19891, 18981) = 2$$$,$$$f(54321, 24361) = 3$$$。

给定两个整数 $$$l$$$ 和 $$$r$$$ 相同 十进制表示的长度。考虑所有整数 $$$l \leq x \leq r$$$。您的任务是找到 $$$f(l, x) + f(x, r)$$$ 的最小值。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例由一行组成,其中包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \lt 10^9$$$)。

保证数字 $$$l$$$ 和 $$$r$$$ 在十进制表示中具有相同的长度,并且没有前导零。

输出

对于每个测试用例,输出所有整数值 $$$l \leq x \leq 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

注意

在第一个测试用例中,您可以选择$$$x = 1$$$。那么 $$$f(1, 1) + f(1, 1) = 1 + 1 = 2$$$。

在第二个测试用例中,您可以选择 $$$x = 2$$$。那么 $$$f(2, 2) + f(2, 3) = 1 + 0 = 1$$$。

在第三个测试用例中,您可以选择$$$x = 5$$$。那么 $$$f(4, 5) + f(5, 6) = 0 + 0 = 0$$$。

在第四个测试用例中,您可以选择$$$x = 15$$$。那么 $$$f(15, 15) + f(15, 16) = 2 + 1 = 3$$$。

在第五个测试用例中,您可以选择$$$x = 18$$$。那么 $$$f(17, 18) + f(18, 19) = 1 + 1 = 2$$$。

在第六个测试用例中,您可以选择$$$x = 200$$$。那么 $$$f(199, 200) + f(200, 201) = 0 + 2 = 2$$$。

在第七个测试用例中,您可以选择$$$x = 900$$$。那么 $$$f(899, 900) + f(900, 999) = 0 + 1 = 1$$$。

在第八个测试用例中,您可以选择$$$x = 1992$$$。那么 $$$f(1990, 1992) + f(1992, 2001) = 3 + 0 = 3$$$。