Palindrome-Free Numbers

Time limit1sMemory limit128 MB

Summary

Count integers in [a, b] whose decimal representation has no palindromic substring of length 2 or more.

Level: Medium7 of 10
Topics: Dynamic programming, Implementation, Math, Brute force
Solved: No attempts yet

Problem

A string is called a palindrome if it reads the same forwards and backwards.

Write the decimal representation of an integer $A$ as a string of digits. If none of its substrings of length $2$ or more (contiguous digits) is a palindrome, then $A$ is called a palindrome-free number.

For example, $16276$ is a palindrome-free number. On the other hand, $17276$ is not, because its substring $727$ is a palindrome.

Given two integers $a$ and $b$ , write a program that counts how many palindrome-free numbers lie between $a$ and $b$ , inclusive.

Input

The first line contains two integers $a$ and $b$ , separated by a space. ( $0 \le a \le b \le 10^{18}$ )

Output

Print, on the first line, the number of palindrome-free integers that are at least $a$ and at most $b$ .

Examples4

Example 1
Input
```
123 321
```
Expected output
```
153
```
Example 2
Input
```
0 0
```
Expected output
```
1
```
Example 3
Input
```
0 9
```
Expected output
```
10
```
Example 4
Input
```
0 10
```
Expected output
```
11
```