PR003004 - Digit Sum

no tags 

 

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].

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

hide comments
dwij28: 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 ?

nitin jain: 2016-01-23 19:22:45

just ctrl c and ctrl v !! CPRC1C

sonupmandal: 2016-01-23 19:18:37

copy paste CPCRC1C and got AC in one go......:-)

Yash: 2015-07-04 17:01:24

CPCRC1C accepted but NZEC here :(

fitcat: 2013-11-28 05:39:02

Same as CPCRC1C except with higher upper limit.


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