快乐数计数

题目描述:

定义 S(x) 是正整数 x 十进制各个数位上数字的平方和。

我们称正整数 x 是快乐数，若 S(x) 是快乐数或 x=1。

请你求出区间 [L, R] 里的快乐数有多少个。

输入格式:

你需要回答多组询问，第一行一个正整数 T，表示询问数量。

接下来 T 行，每行两个正整数 L, R。

输出格式:

T 行，每行一个正整数，表示 [L, R] 内快乐数的个数。

样例输入:

3
1 10
5 20
7 100

样例输出:

3
4
19

提示:

数据范围：询问数量 T 不超过 100.

1 ≤ L ≤ R < 10⁵⁰

部分分：对于 40% 的数据，R ≤ 10000；对于 60% 的数据，R ≤ 10⁷.

时间限制: 1000ms
空间限制: 256MB

---

来源: zhanghao1