불행한 수

시간 제한1초메모리 제한128 MB

요약

[lo, hi] 구간에서 각 자릿수를 제곱해 더하는 과정을 반복해도 1에 도달하지 않는 수의 개수를 센다. 상한이 1e18이라 자릿수 DP가 필요하다. Some contexts make statements clearer, so let me restate it as asked. no

난이도: 어려움10점 중 8점
유형: 수학, 동적 계획법, 비트 연산, 구현
정답자: 아직 제출이 없습니다

문제

수에게도 감정이 있습니다! 임의의 양의 정수에 대해, 각 자리 숫자를 제곱하여 모두 더합니다. 그 결과에 대해 같은 과정을 반복합니다.

이 과정을 유한 번 반복했을 때 합이 $1$ 이 되는 수를 행복한 수(Happy) 라고 합니다. 행복한 수가 $1$ 에 도달하기까지 필요한 반복 횟수를 그 수의 행복까지의 거리 라고 부릅니다. $1$ 의 행복까지의 거리는 $0$ 이고, $23$ 의 행복까지의 거리는 $3$ 입니다. $2^2 + 3^2 = 13$ , 그다음 $1^2 + 3^2 = 10$ , 마지막으로 $1^2 + 0^2 = 1$ 이 되기 때문입니다.

과정을 아무리 반복해도 $1$ 에 도달하지 못하고 같은 값들이 끝없이 순환하는 고리에 갇히는 수를 불행한 수(Unhappy) 라고 합니다. 이러한 수는 행복으로부터 무한히 멀리 떨어져 있습니다.

정수 범위의 하한과 상한이 주어질 때, 그 범위(양 끝 포함) 안에 불행한 수가 몇 개 있는지 구하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 한 줄에 두 양의 정수 $lo$ 와 $hi$ ( $0 < lo \le hi \le 10^{18}$ )가 하나의 공백으로 구분되어 주어집니다. 입력은 두 개의 $0$ 이 있는 줄로 끝나며, 이 종료 줄은 테스트 케이스가 아니므로 처리하지 않습니다.

출력

각 테스트 케이스마다 $lo$ 와 $hi$ 사이(양 끝 포함)에 있는 불행한 수의 개수를 한 줄에 하나의 정수로 출력하세요. 불필요한 공백을 출력하지 말고, 답 사이에 빈 줄을 넣지 마세요.

예제4

예제 1
입력
```
1 10
1 100
0 0
```
예상 출력
```
7
80
```
예제 2
입력
```
1 1
7 7
2 2
0 0
```
예상 출력
```
0
0
1
```
예제 3
입력
```
1 20
0 0
```
예상 출력
```
15
```
예제 4
입력
```
50 100
0 0
```
예상 출력
```
42
```