PR003004 - Digit Sum

For a pair of integers a and b, the digit sum of the interval [a,b] is defined as the sum of all digits occurring in all numbers between (and including) a and b. For example, the digit sum of [28, 31] can be calculated as:

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

Given the numbers a and b, calculate the digit sum of [a,b].

Input

On the first line one positive number: the number of test cases, at most 100.

After that per test case:

  • one line with two space-separated integers, a and b (0 <= a <= b <= 10^15).

Output

Per test case:

  • one line with an integer: the digit sum of [a,b];

Example

Input:
3
0 10
28 31
1234 56789

Output:
46
28
1128600

Added by:kojak_
Date:2013-11-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:BAPC

hide comments
2019-12-05 11:20:16
Hmm weird, I got WA for CRCRC1C, but got AC for this one with literally the same code.
2018-02-04 13:04:47 Akshay Aradhya
LOL I forgot to change my DP memory from CPCRC1C.
Changed it and AC :)
2016-06-29 11:58:48
Answer should technically always fit in the range of long long int. But my C++ solution gives a WA but its exact 100% translation into python gives AC. Can someone tell me what could be the reason behind it ?
2016-01-23 19:22:45 nitin jain
just ctrl c and ctrl v !! CPRC1C
2016-01-23 19:18:37
copy paste CPCRC1C and got AC in one go......:-)
2015-07-04 17:01:24 Yash
CPCRC1C accepted but NZEC here :(
2013-11-28 05:39:02 fitcat
Same as CPCRC1C except with higher upper limit.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.