The Polar Express

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Mimi has just won two raffle tickets for the Polar Express! Unfortunately, there is just one obstacle in the way — the skill testing question!

Let us define \operatorname S(x) to be the sum of digits of x. Given two positive integers, L and R, compute the number of distinct values of \operatorname S(x), for x = L,L+1, \ldots R-1,R.

Mimi has agreed to give you the other ticket if you help her solve this problem. Can you do it?

Constraints

Subtask 1 [10%]

1 \le L \le R \le 10^5

Subtask 2 [90%]

1 \le L \le R \le 10^{18}

Input Specification

The first and only line of input will contain two space separated integers, L and R.

Output Specification

A single integer, the number of distinct values of \operatorname S(x).

Sample Input

19 28

Sample Output

9

Comments

There are no comments at the moment.