Guided by the highly intelligent red-headed slime known as the "Slime Mentor," the slimes have learned decimal numbers and are able to use them for divination.

Slimes perform divination every day. The process for day $k$ is as follows:

1. Set the value of $n$ to $k$.
2. Write down the decimal representation of $n$ without leading zeros. If some numbers have already been written down, append $n$ to the end of them.
3. Let $n := n - S(n)$, where $S(n)$ denotes the sum of the digits of $n$ in its decimal representation. For example, $S(233) = 2+3+3=8$, and $S(114514) = 1+1+4+5+1+4=16$.
4. If $n=0$, the divination ends; otherwise, return to step 2.

The final divination result is a decimal digit string. Obviously, it also represents a decimal number. The slimes want you to help them calculate the sum of the divination results from day $L$ to day $R$. Since the answer may be very large, you only need to output the result modulo $998244353$. The slimes have asked $T$ such questions in total, and you need to find the answer for each question.

Input

The first line contains a positive integer $T$, representing the number of questions from the slimes.

The next $T$ lines each contain two positive integers $L$ and $R$, representing the range of days for which you need to calculate the sum of the divination results.

Output

For each query, output the answer modulo $998244353$.

Examples

Input 1

7
1 9
10 11
32 32
16058 258258
1 998244353
31415926 271828182
757427636498525616 1000000000000000000

Output 1

45
228
3227189
64050837
32261615
188342047
329553393

Note

For $1 \le k \le 9$, the divination on day $k$ ends after one step, so the result is $k$. The answer for the first query is $1+2+3+\dots+9=45$.

On day $10$, the divination writes down $10$ and $10-S(10)=9$ in sequence. On day $11$, it writes down $11$ and $9$ in sequence. Thus, the answer for the second query is $109+119=228$.

On day $32$, it writes down $32$, $32-S(32)=27$, $27-S(27)=18$, and $18-S(18)=9$ in sequence. Therefore, the answer for the third query is $3227189$.

Constraints

Subtask 1 (5 pts): $T \le 500, R \le 10^5$.

Subtask 2 (10 pts): $T \le 5, L=R \le 10^9$.

Subtask 3 (20 pts): $T \le 500, L=R \le 10^{12}$.

Subtask 4 (30 pts): $L=R$.

Subtask 5 (10 pts): $T \le 500, R \le 10^{12}$.

Subtask 6 (25 pts): No special constraints.

For all test cases, $1 \le T \le 5 \times 10^4$ and $1 \le L \le R \le 10^{18}$.