310442: CF1834B. Maximum Strength

B. Maximum Strengthtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Fedya is playing a new game called "The Legend of Link", in which one of the character's abilities is to combine two materials into one weapon. Each material has its own strength, which can be represented by a positive integer $x$. The strength of the resulting weapon is determined as the sum of the absolute differences of the digits in the decimal representation of the integers at each position.

Formally, let the first material have strength $X = \overline{x_{1}x_{2} \ldots x_{n}}$, and the second material have strength $Y = \overline{y_{1}y_{2} \ldots y_{n}}$. Then the strength of the weapon is calculated as $|x_{1} - y_{1}| + |x_{2} - y_{2}| + \ldots + |x_{n} - y_{n}|$. If the integers have different lengths, then the shorter integer is padded with leading zeros.

Fedya has an unlimited supply of materials with all possible strengths from $L$ to $R$, inclusive. Help him find the maximum possible strength of the weapon he can obtain.

An integer $C = \overline{c_{1}c_{2} \ldots c_{k}}$ is defined as an integer obtained by sequentially writing the digits $c_1, c_2, \ldots, c_k$ from left to right, i.e. $10^{k-1} \cdot c_1 + 10^{k-2} \cdot c_2 + \ldots + c_k$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 500$). The description of the test cases follows.

The first line of each test case contains two integers $L$ and $R$ ($1 \le L \le R < 10^{100}$) — the decimal representation of the integers representing the minimum and maximum strength of the materials that Fedya has. It is guaranteed that the integers $L$ and $R$ do not contain leading zeros.

Note that the input data may not fit into standard $32$-bit or $64$-bit integer data types.

Output

For each test case print one integer — the maximum possible strength of the weapon that Fedya can obtain from the given materials.

ExampleInput

6
53 57
179 239
13 37
132228 132228
54943329752812629795 55157581939688863366
88 1914

Output

4
19
11
0
163
28

Note

In the first test case, the weapon made from materials with strengths $53$ and $57$ will have the maximum possible strength: $|5 - 5| + |3 - 7| = 4$.

In the second test case, the maximum strength is achieved with materials with strengths $190$ and $209$: $|1 - 2| + |9 - 0| + |0 - 9| = 19$.

In the fourth test case, there is only one valid strength, so the answer is $0$.

In the sixth test case, the maximum strength is achieved with materials with strengths $1909$ and $90$: $|1 - 0| + |9 - 0| + |0 - 9| + |9 - 0| = 28$. Note that the shorter integer was padded with leading zeros.

题目大意：
Fedya 在玩一个名为 "The Legend of Link" 的新游戏，其中一个角色的能力是将两种材料合成一件武器。每种材料都有自己的强度，可以用正整数 x 表示。合成武器的基础强度由整数各位数字之差的绝对值之和确定。

具体来说，设第一种材料的强度为 X = x1x2...xn，第二种材料的强度为 Y = y1y2...yn，则合成武器的强度计算为 |x1 - y1| + |x2 - y2| + ... + |xn - yn|。如果两个整数的长度不同，则较短的整数会在前面补零。

Fedya 可以使用强度从 L 到 R 的所有材料（包括 L 和 R），帮助他找到可以获得的武器最大强度。

输入输出数据格式：
输入：
- 第一行包含一个整数 t（1 ≤ t ≤ 500），表示测试用例的数量。
- 每个测试用例包含一行，有两个整数 L 和 R（1 ≤ L ≤ R < 10^100），分别表示可用的材料的最小和最大强度。保证 L 和 R 不包含前导零。
- 注意，输入数据可能不适合标准的 32 位或 64 位整数数据类型。

输出：
- 对于每个测试用例，输出一行，包含 Fedya 可以从给定材料获得武器的最大可能强度。

示例输入输出：
输入：
```
6
53 57
179 239
13 37
132228 132228
54943329752812629795 55157581939688863366
88 1914
```
输出：
```
4
19
11
0
163
28
```

注意：
- 在第一个测试用例中，使用强度为 53 和 57 的材料合成的武器具有最大强度：|5 - 5| + |3 - 7| = 4。
- 在第二个测试用例中，使用强度为 190 和 209 的材料合成的武器具有最大强度：|1 - 2| + |9 - 0| + |0 - 9| = 19。
- 在第四个测试用例中，只有一个有效强度，所以答案为 0。
- 在第六个测试用例中，使用强度为 1909 和 90 的材料合成的武器具有最大强度：|1 - 0| + |9 - 0| + |0 - 9| + |9 - 0| = 28。注意较短的整数被补了前导零。题目大意： Fedya 在玩一个名为 "The Legend of Link" 的新游戏，其中一个角色的能力是将两种材料合成一件武器。每种材料都有自己的强度，可以用正整数 x 表示。合成武器的基础强度由整数各位数字之差的绝对值之和确定。 具体来说，设第一种材料的强度为 X = x1x2...xn，第二种材料的强度为 Y = y1y2...yn，则合成武器的强度计算为 |x1 - y1| + |x2 - y2| + ... + |xn - yn|。如果两个整数的长度不同，则较短的整数会在前面补零。 Fedya 可以使用强度从 L 到 R 的所有材料（包括 L 和 R），帮助他找到可以获得的武器最大强度。 输入输出数据格式： 输入： - 第一行包含一个整数 t（1 ≤ t ≤ 500），表示测试用例的数量。 - 每个测试用例包含一行，有两个整数 L 和 R（1 ≤ L ≤ R < 10^100），分别表示可用的材料的最小和最大强度。保证 L 和 R 不包含前导零。 - 注意，输入数据可能不适合标准的 32 位或 64 位整数数据类型。 输出： - 对于每个测试用例，输出一行，包含 Fedya 可以从给定材料获得武器的最大可能强度。 示例输入输出： 输入： ``` 6 53 57 179 239 13 37 132228 132228 54943329752812629795 55157581939688863366 88 1914 ``` 输出： ``` 4 19 11 0 163 28 ``` 注意： - 在第一个测试用例中，使用强度为 53 和 57 的材料合成的武器具有最大强度：|5 - 5| + |3 - 7| = 4。 - 在第二个测试用例中，使用强度为 190 和 209 的材料合成的武器具有最大强度：|1 - 2| + |9 - 0| + |0 - 9| = 19。 - 在第四个测试用例中，只有一个有效强度，所以答案为 0。 - 在第六个测试用例中，使用强度为 1909 和 90 的材料合成的武器具有最大强度：|1 - 0| + |9 - 0| + |0 - 9| + |9 - 0| = 28。注意较短的整数被补了前导零。