Youngsik Function

Time limit2sMemory limit128 MB

Summary

Count integers in [A, B] up to 1e9 whose repeated adjacent-digit-difference reduction (the Youngsik function) eventually collapses to the single digit 7.

Level: Medium7 of 10
Topics: Dynamic programming, Recursion, Math, Simulation
Solved: No attempts yet

Problem

For a natural number N with at least two digits, define the Youngsik function F(N) as follows.

F(N) is the number made by writing, from left to right, the differences between each pair of adjacent digits of N. Each difference is the larger digit minus the smaller digit. For example, F(5913) = 482, F(1198) = 081 = 81, and F(666) = 00 = 0.

Starting from a natural number N, repeatedly form the sequence N, F(N), F(F(N)), ... until a one-digit number first appears. That last one-digit number is called the fingerprint of N. For example, when N = 5913, the sequence is 5913, 482, 46, 2, so the fingerprint of 5913 is 2.

A number is lucky if its fingerprint is 7. Count how many lucky numbers are between A and B, inclusive.

Input

The first line contains two natural numbers A and B separated by a space.

1 <= A <= B <= 1,000,000,000.

Output

Print the number of lucky numbers between A and B, inclusive.

Hint

From 1 through 100, the lucky numbers are 7, 18, 29, 70, 81, and 92, for a total of 6.

Examples6

Example 1
Input
```
1 100
```
Expected output
```
6
```
Example 2
Input
```
1 9
```
Expected output
```
1
```
Example 3
Input
```
1198 1198
```
Expected output
```
1
```
Example 4
Input
```
1223 1299
```
Expected output
```
0
```
Example 5
Input
```
999999930 1000000000
```
Expected output
```
2
```
Example 6
Input
```
100000 1000000000
```
Expected output
```
159720
```