digits-3

We perform the following operation on a positive integer: we sort its digits in ascending order — removing any leading zeros — then subtract the product of its digits from that number. For example:
3213210 ⟶ 0112233 ⟶ 112233-36 = 112197
We repeat this process with each resulting number until we get zero:
1231230 ⟶ 112197 ⟶ 111153 ⟶ 111120 ⟶ 11110 ⟶ 1110 ⟶ 110 ⟶ 10 ⟶ 0
How many steps does it take to reach zero? What is the maximum number of steps ($M$) for all integers in an interval $[L, R] (L ≤ R)$ ?

Input specification

The first line contains $T$, the number of test cases. Then $T$ lines follow, each containing the numbers $L_k$ and $R_k~~(k = 1,\ldots,T)$.

Output specification

Output $T$ lines, each containing the required value $M_k~~(k = 1,\ldots T)$.

Constraints

$1\le T \le 100$
$1\le L_k \le 1\_000\_000\_000\_000$
$1\le R_k \le 1\_000\_000\_000\_000$
$0\le R_k-L_k \le 100\_000~~~(k=1,\ldots,T)$
Solving smaller subtasks will yield partial points.

Sample input 1

1. 5
2. 1 99
3. 100 9999
4. 10000 100000
5. 1231230 1233210
6. 56875687 56875687

Sample output 1

1. 4
2. 11
3. 13
4. 13
5. 11