← 返回题目列表

Codeforces · 1808/C

C. 不吉利的数字

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

在这个问题中,与问题 A 不同,你需要寻找最不幸的数字,而不是最幸运的数字。

请注意,该问题的约束与问题 A 中的约束不同。

奥林巴斯城最近启动了个人星舰的生产。现在火星上的每个人都可以购买一架并以便宜的价格飞往其他星球。

每艘星舰都有一个编号——某个正整数 $$$x$$$。让我们将数字 $$$x$$$ 的幸运程度定义为该数字的最大数字与最小数字之间的差值。例如,$$$142857$$$的最大位数为$$$8$$$,最小位数为$$$1$$$,因此它的幸运值是$$$8-1=7$$$。而数字 $$$111$$$ 的所有数字都等于 $$$1$$$,因此它的运气为零。

Hateehc是一位著名的火星博主,经常飞往太阳系的不同角落。为了更快地发布有趣的视频,他决定给自己买一艘星际飞船。当他来到商店时,看到了一艘艘星舰,上面的数字从$$$l$$$到$$$r$$$(含)。在商店里,Hateehc 想要找到一艘号码最不吉利的星舰。

由于商店里有很多星舰​​,而 Hateehc 不会编程,所以你必须帮助博主编写一个程序来回答他的问题。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 600$$$) — 测试用例的数量。

以下 $$$t$$$ 行中的每一行都包含测试用例的描述。描述由两个整数 $$$l$$$、$$$r$$$ ($$$1 \le l \le r \le 10^{18}$$$) 组成 - 商店中星舰的最大和最小数量。

输出

打印 $$$t$$$ 行,每个测试用例一行,包含商店中最不幸的星舰编号。

如果有多种方法可以选择最不幸的数字,则输出其中任何一种。

示例

输入 #1

5
59 63
42 49
48 53
90 90
1 100

输出 #1

63
44
53
90
1

注意

让我们看两个测试示例:

- 数字 $$$59$$$ 的幸运值是 $$$9 - 5 = 4$$$;
- $$$60$$$ 的幸运值等于 $$$6 - 0 = 6$$$;
- $$$61$$$ 的幸运值等于 $$$6 - 1 = 5$$$;
- $$$62$$$ 的幸运值等于 $$$6 - 2 = 4$$$;
- $$$63$$$ 的幸运值是 $$$6 - 3 = 3$$$。

在第五个测试用例中,最不幸的数字是 $$$1$$$、$$$2$$$、$$$3$$$、$$$4$$$、$$$5$$$、$$$6$$$、$$$7$$$、$$$8$$$、$$$9$$$、$$$11$$$、$$$22$$$、 $$$33$$$、$$$44$$$、$$$55$$$、$$$66$$$、$$$77$$$、$$$88$$$、$$$99$$$,因此您可以选择其中任何一个。