Background

The difference between this problem and P13085 [SCOI2009] windy 数（加强版） is the ranges of $\bm{a}$ and $\bm{b}$.

Windy defined a kind of "windy number".

Problem Description

A positive integer without leading zeros, where the absolute difference between every pair of adjacent digits is at least $2$, is called a windy number. Windy wants to know: between $a$ and $b$, inclusive, how many windy numbers are there?

Input Format

The input contains a single line with two integers, representing $a$ and $b$.

Output Format

Output a single line with one integer, the answer.

1 10

9

25 50

20

Hint

Constraints

For all test points, it is guaranteed that $1 \leq a \leq b \leq 2 \times 10^9$.

Translated by ChatGPT 5