21640번 - Hard Work 다국어

Alexey works as a mathematician in a well-known company "WordCount". Since his project has been recently closed, he was given a rather strange kind of assignment as a replacement: he must write down consecutive integers in a certain range every month, and at the end of the month the accounting department makes some calculations that determine Alexey's salary.

Alexey's salary is calculated as follows: first, the accounting department finds such $x$ that there exists an integers with $x$ identical consecutive digits that among the integers that Alexey has written down, but there is no integer with $x+1$ identical consecutive digits. Then the integers that have $x$ identical consecutive digits are counted and the resulting amount is the Alexey's salary.

Alexey is a smart mathematician so he doesn't want to work for peanuts. Today he was given a work plan for the next $t$ months. During the $i$-th month he must write down integers from $l_i$ to $r_i$ inclusive. Help Alexey to calculate, what his salary would be each month, if the accounting department always does its calculations right.

The first line of input contains a single integer $t$, the number of months for which Alexey's salary should be calculated ($1 \le t \le 10^4$).

The $i$-th of the following $t$ lines contains two space-separated integers $l_i$ and $r_i$, the first and the last integer Alexey will write down during the $i$-th month ($1 \le l_i \le r_i \le 10^{18}$).

For each given month you should print a line with the calculated value of $x$ and Alexey's salary for that month.

Alexey writes down integers from $312$ and $348$ in the first example. There is an integer $333$ that has three identical consecutive digits. There are no other integers between those that have three identical consecutive digits, so the answer is "3 1".

In the second example, there are no integers with three identical consecutive digits between $223$ and $329$. The integers with two identical consecutive digits can be divided into three groups:

• $\overline{22x}$ (from $223$ to $229$)
• $\overline{2xx}$ (from $233$ to $299$)
• $\overline{3xx}$ ($300$, $311$ and $322$)

There are exactly $17$ integers so the answer is "2 17".