CPCRC1C - Sum of Digits

Majid is a 3rd-grade elementary student and quite well in mathematics. Once, Majid's teacher asked him to calculate the sum of numbers 1 through n.

Majid quickly answered, and his teacher made him another challenge. He asked Majid to calculate the sum of the digits of numbers 1 through n.

Majid did finally find the solution. Now it is your turn, can you find a solution?

Input

Two space-separated integers 0 <= a <= b <= 109.

Program terminates if a and b are -1.

Output

The sum of the digits of numbers a through b.

Example

Input:
1 10
100 777
-1 -1

Output:
46
8655

Added by:Tii
Date:2010-10-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:http://cs.ikiu.ac.ir/cms/icpc/training/7-contest/86-contest1

hide comments
2017-11-22 07:51:05 herkeyrefugee
Good one pure math!!Finally AC
2017-09-27 11:06:21
wooooo !!!!! learned a new thing "DIGIT DP" :-)
2017-08-25 08:59:32
Do with digit DP
2017-07-13 14:54:45
I don't know why I'm getting WA though my code passes every test case....those present on spojtoolkit as well...
Edit : Finally got AC on 4th attempt...a silly mistake cost me 3 WA

Last edit: 2017-07-13 15:31:23
2017-06-28 21:11:12
Very Nice Problem!!
learned new thing :-)
2017-06-24 00:32:54
Digit Dp :)
2017-05-30 08:54:06
Even if you solve this problem without dp, just look for "Digit Dynamic Programming" and you will learn something good. Have fun:)
2017-04-02 01:12:35
Great one! AC in one go!
2017-03-26 22:07:43
Learned new thing!!
2017-03-25 08:12:12
i think the answer for test case 100 777 must be 8107 instead of 8655
please correct me if i,m wrong
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.