310274: CF1808C. Unlucky Numbers

C. Unlucky Numberstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

In this problem, unlike problem A, you need to look for unluckiest number, not the luckiest one.

Note that the constraints of this problem differ from such in problem A.

Olympus City recently launched the production of personal starships. Now everyone on Mars can buy one and fly to other planets inexpensively.

Each starship has a number —some positive integer $x$. Let's define the luckiness of a number $x$ as the difference between the largest and smallest digits of that number. For example, $142857$ has $8$ as its largest digit and $1$ as its smallest digit, so its luckiness is $8-1=7$. And the number $111$ has all digits equal to $1$, so its luckiness is zero.

Hateehc is a famous Martian blogger who often flies to different corners of the solar system. To release interesting videos even faster, he decided to buy himself a starship. When he came to the store, he saw starships with numbers from $l$ to $r$ inclusively. While in the store, Hateehc wanted to find a starship with the unluckiest number.

Since there are a lot of starships in the store, and Hateehc can't program, you have to help the blogger and write a program that answers his question.

Input

The first line contains an integer $t$ ($1 \le t \le 600$) —the number of test cases.

Each of the following $t$ lines contains a description of the test case. The description consists of two integers $l$, $r$ ($1 \le l \le r \le 10^{18}$) — the largest and smallest numbers of the starships in the store.

Output

Print $t$ lines, one line for each test case, containing the unluckiest starship number in the store.

If there are several ways to choose the unluckiest number, output any of them.

ExampleInput

5
59 63
42 49
48 53
90 90
1 100

Output

63
44
53
90
1

Note

Let's look at two test examples:

• the luckiness of the number $59$ is $9 - 5 = 4$;
• the luckiness of $60$ equals $6 - 0 = 6$;
• the luckiness of $61$ equals $6 - 1 = 5$;
• the luckiness of $62$ equals $6 - 2 = 4$;
• the luckiness of $63$ is $6 - 3 = 3$.

So the unluckiest number is $63$.

In the fifth test case, the unluckiest numbers are $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$, $11$, $22$, $33$, $44$, $55$, $66$, $77$, $88$, $99$, so you are allowed to choose any of them.

题目大意：
本题的目标是寻找“最不幸的数字”，与问题A中的“最幸运的数字”不同。奥林匹斯城最近开始生产个人星际飞船，每个飞船都有一个正整数编号x。定义数字x的“幸运度”是该数字的最大数字和最小数字之差。例如，142857的最大数字是8，最小数字是1，因此它的幸运度是7。而数字111的所有数字都是1，所以它的幸运度是0。题目中给出t个测试案例，每个案例包含两个整数l和r，要求输出每个案例中区间[l, r]内最不幸的数字。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 ≤ t ≤ 600），表示测试案例的数量。
- 接下来的t行，每行包含两个整数l和r（1 ≤ l ≤ r ≤ 10^18），表示飞船编号的区间。

输出：
- 输出t行，每行对应一个测试案例的结果，输出区间[l, r]内最不幸的数字。
- 如果存在多个最不幸的数字，输出其中任意一个。题目大意： 本题的目标是寻找“最不幸的数字”，与问题A中的“最幸运的数字”不同。奥林匹斯城最近开始生产个人星际飞船，每个飞船都有一个正整数编号x。定义数字x的“幸运度”是该数字的最大数字和最小数字之差。例如，142857的最大数字是8，最小数字是1，因此它的幸运度是7。而数字111的所有数字都是1，所以它的幸运度是0。题目中给出t个测试案例，每个案例包含两个整数l和r，要求输出每个案例中区间[l, r]内最不幸的数字。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 ≤ t ≤ 600），表示测试案例的数量。 - 接下来的t行，每行包含两个整数l和r（1 ≤ l ≤ r ≤ 10^18），表示飞船编号的区间。 输出： - 输出t行，每行对应一个测试案例的结果，输出区间[l, r]内最不幸的数字。 - 如果存在多个最不幸的数字，输出其中任意一个。