Odometer

Interview

Time limit1sMemory limit128 MB

Summary

Count the integers between X and Y whose decimal digits use one repeated digit except for a single different digit.

Level: Medium5 of 10
Topics: Brute force, Combinatorics
Solved: No attempts yet

Problem

Farmer John's cows are on a road trip. The car odometer shows an integer mileage value, starting at $X$ ( $100 \le X \le 10^{16}$ ) miles and ending at $Y$ ( $X \le Y \le 10^{16}$ ) miles. The cows moo whenever the odometer shows an interesting number, including at the start and end of the trip.

After ignoring leading zeros, look at the remaining digits. A number is interesting if exactly one digit differs and every other digit is the same. For example, $33323$ and $110$ are interesting, while $9779$ and $55555$ are not.

Count how many times the cows moo during the trip.

Input

Line 1: two integers $X$ and $Y$ , separated by a space

Output

Line 1: the number of times the cows moo during the trip

Hint

An interesting number uses exactly two distinct digits, with one digit appearing once and the other digit filling the remaining positions. Values up to $10^{16}$ fit in a 64-bit integer.

Examples3

Example 1
Input
```
110 133
```
Expected output
```
13
```
Example 2
Input
```
100 100
```
Expected output
```
1
```
Example 3
Input
```
111 111
```
Expected output
```
0
```