問題文

正整数 $n$ に対し、 $f(n)$ を「$n$ を十進表記したときに含まれる数字の最大値」と定義します。
例えば、 $f(314) = 4, ~ f(10) = 1, ~ f(998244353) = 9$ です。

正整数 $L, R ~ (L \leq R)$ が与えられるので、 $f(L) + f(L + 1) + \cdots + f(R)$ の値を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

制約

• 入力される値はすべて整数
• $1 \leq T \leq 10^5$
• $1 \leq L \leq R \leq 10^{17}$

入力

入力は以下の形式で標準入力から与えられる。ここで、$t ~ (1 \leq t \leq T)$ 番目のテストケースを $\mathrm{case}_t$ と表す。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各テストケースは以下の形式で与えられる。

$L$ $R$

出力

$T$ 行出力し、 $t$ 行目には $t$ 番目のテストケースについての答えを出力せよ。

サンプル

3
58 60
5 5
1 100000000000000000

23
5
880820681064622696