Unhappy Numbers

Time limit1sMemory limit128 MB

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.