Odometer

Time limit1sMemory limit128 MB

Summary

Count the integers from X to Y with one digit occupying at least half of their decimal digits, ignoring leading zeros.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

The odometer goes from $X$ to $Y$ . The cows moo whenever it shows an 'interesting' number, including at start and end. A number is interesting if, ignoring leading zeros, at least half of its digits are the same. Examples: 3223 and 110 are interesting; 97791 and 123 are not.

Input

One line with $X$ and $Y$ ( $100 \le X \le Y \le 10^{18}$ ).

Output

Print how many times the cows moo.

Examples1

Example 1
Input
```
110 133
```
Expected output
```
14
```