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
2022-08-25 08:05:45
easy one. :)
2022-08-15 18:02:03
can someone tell me if i use vector of vector as dp table it gives wa but if i use global 2d array it gives ac why?
2022-03-08 18:03:38
@dwij28 I had the same problem when I found that I was unintentionally converting long long int into int . Maybe you have the same problem in your code. I tried solving for 10^15 and the output was coming out to be zero, you can also try for the same value.
2021-08-27 17:58:40
Unsigned Long Long for the wins
Thanks to everyone who commented about this and helped me save time
2021-07-06 11:36:58
getting wrong answer on using long long in c++

Last edit: 2021-07-06 16:37:45
2021-07-06 11:35:03
@dwij28 instead of long long, use unsigned long long int
2021-04-29 19:44:29
Getting wrong answer.

[NG]: For the sample cases you provided, you're getting correct results. Don't post any code in the comments, use forum for code review and debug.

Last edit: 2021-04-30 11:51:34
2020-12-24 13:15:36
easy peasy ...
2020-05-20 16:13:01
can anyone help me iam getting tle tried code of gfg digit sum plz give any link for studying
2020-02-09 20:05:37
this problem have something rare. I have the same situation as dwij28, 3 comments below
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.