Problem B
Happy and Unhappy Numbers
It turns out there are such things as happy numbers and unhappy numbers. We’re going to assume that you have been using these poor little lovable creatures your whole life with absolutely no consideration for their feelings and general well-being. Perhaps today we can convince you to have some empathy and to stop and think about whether or not your numbers are happy. Who ever said that a programming competition cannot be a lesson in numerical ethics?
A happy number is a positive integer that, when repeatedly replaced with the sum of the squares of its digits, eventually reaches the number $1$. Alternatively, if this process repeats endlessly, the number is unhappy.
Slightly more formally (taken from Wikipedia), given a positive integer $n = n_{0}$, define a sequence $n_{0}, n_{1}, n_{2}, \ldots $, where $n_{j+1}$ is the sum of the squares of the base-$10$ digits of $n_{j}$, for $j \geq 0$. Then $n$ is happy if and only if there exists $i \geq 0$ such that $n_{i} = 1$; otherwise, $n$ is unhappy.
If you are still confused, take a look at the process for the number $19$, which is happy:
\[ 1^{2} + 9^{2} = 82 \]\[ 8^{2} + 2^{2} = 68 \]\[ 6^{2} + 8^{2} = 100 \]\[ 1^{2} + 0^{2} + 0^{2} = 1 \]Given two positive integers, $A$ and $B$ (with $A \leq B$), your challenge is to determine how many happy numbers there are between $A$ and $B$ (inclusive).
Input
The first line of input contains a single integer, $T$ ($1 \leq T \leq 10\, 000$), the number of test cases. This is followed by $T$ lines, one per test case. Each test case is specified by two space-separated integers, $A$ and $B$ ($1 \leq A \leq B \leq 10^{6}$).
Output
For each test case, output a single line containing the number of happy numbers between $A$ and $B$, inclusive.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 1 20 14 18 |
5 0 |
