Unhappy Numbers

Time limit1sMemory limit128 MB

Summary

Count numbers in [lo, hi] that never reach 1 under the digit-square-sum map; bounds go up to 1e18 so answers need digit DP over precomputed unhappy states.

Level: Hard8 of 10
Topics: Math, Dynamic programming, Bit manipulation, Implementation
Solved: No attempts yet

Problem

Numbers have feelings too! For any positive integer, square each of its digits and add the squares together. Take that result and repeat the same process.

A number is Happy if, after repeating this process a finite number of times, the sum becomes $1$ . The number of iterations a happy number needs to reach $1$ is called its distance from happiness: the distance from happiness of $1$ is $0$ , and the distance from happiness of $23$ is $3$ , because $2^2 + 3^2 = 13$ , then $1^2 + 3^2 = 10$ , and finally $1^2 + 0^2 = 1$ .

A number is Unhappy if it is infinitely far from happiness: the process never reaches $1$ and instead gets stuck in a repeating loop.

Given the lower and upper bounds of a range of integers, determine how many Unhappy numbers lie in that range (inclusive).

Input

The input contains several test cases. Each test case is a single line with two positive integers $lo$ and $hi$ ( $0 < lo \le hi \le 10^{18}$ ), separated by a single space. The input ends with a line containing two zeros; this terminating line is not a test case and must not be processed.

Output

For each test case, print a single integer on its own line: the count of Unhappy numbers between $lo$ and $hi$ (inclusive). Print no extra spaces, and do not separate answers with blank lines.

Examples4

Example 1
Input
```
1 10
1 100
0 0
```
Expected output
```
7
80
```
Example 2
Input
```
1 1
7 7
2 2
0 0
```
Expected output
```
0
0
1
```
Example 3
Input
```
1 20
0 0
```
Expected output
```
15
```
Example 4
Input
```
50 100
0 0
```
Expected output
```
42
```