Digit Sum of a Range

Interview

Time limit1sMemory limit128 MB

Summary

For each query [a,b] with b up to 10^15, output the sum of all decimal digits of every integer in the range.

Level: Medium6 of 10
Topics: Math, Dynamic programming, Implementation, Prefix sum
Solved: No attempts yet

Problem

The digit sum of a range $[a, b]$ is the sum of every digit of every integer contained in that range. For example, the digit sum of the range $[28, 31]$ is:

$2+8 + 2+9 + 3+0 + 3+1 = 28$

Given two integers $a$ and $b$ , write a program that computes the digit sum of the range $[a, b]$ .

Input

The first line contains the number of test cases $T$ . ( $T \le 100$ )

Each of the next $T$ lines contains one test case: two integers $a$ and $b$ separated by a space. ( $0 \le a \le b \le 10^{15}$ )

Output

For each test case, print the digit sum of the range $[a, b]$ on its own line.

Examples1

Example 1
Input
```
3
0 10
28 31
1234 56789
```
Expected output
```
46
28
1128600
```