28423번 - 게임

문제

수학을 잘하는 랑이는 오늘 집사에게 수를 이용한 게임을 배웠다. 이 게임은 양의 정수 $N$을 초깃값으로 가진 상태로 시작한다. $N$의 각 자릿수를 모두 더한 값을 $A,ドル $N$의 각 자릿수를 모두 곱한 값을 $B$라고 할 때, $A$와 $B$를 순서대로 이어 붙인 수를 $f(N)$으로 표현한다. 예를 들어 $N = 12352$라면 각 자릿수의 합은 1ドル + 2 +たす 3 +たす 5 +たす 2 =わ 13,ドル 각 자릿수의 곱은 1ドル \times 2 \times 3 \times 5 \times 2 = 60$이니 $f(N)$은 이 둘을 순서대로 이어 붙인 1360ドル$이 된다. 1360ドル$에 다시 위 연산을 적용한다면 1ドル + 3 + 6 + 0 = 10,ドル 1ドル \times 3 \times 6 \times 0 = 0$이므로 $f(1360) = 100$이 된다. 이 100ドル$에 다시 연산을 적용하면 $f(100) = 10$이고, 이 결과에 다시 적용한다면 $f(10) = 10$이 된다. 이 게임에서는 $N$이 주어질 때 $f(N),ドル $f(f(N)),ドル $f(f(f(N))),ドル $\cdots$ 형태로 계속 나아갈 때 언젠가 $f(x) = x$ 형태가 되는 $x$가 나올 수 있는지 알아내는 것이 중요하다.

$N$에 연산을 계속 적용해서 $x = f(x)$가 되는 $x$가 나오게 된다면 $g(N) = 1,ドル 나오지 않는다면 $g(N) = 0$으로 표현하자. 단, $N, f(N), f(f(N)), \cdots$ 중 100ドル,000円$보다 큰 수가 하나라도 존재한다면 계산하기 어려우므로 $g(N) = -1$이라고 표현한다. 예를 들어, $N = 1$이라면 $f(1) = 11,ドル $f(11) = 21,ドル $f(21) = 32,ドル $f(32) = 56,ドル $f(56) = 1130,ドル $f(1130) = 50,ドル $f(50) = 50$ 으로 50ドル$에서 $f(x) = x$ 형태가 나오기 때문에 $g(1) = 1$이 된다.

양의 정수 $L, R (L \le R)$이 주어질 때, $g(L) + g(L + 1) + g(L + 2) + \cdots + g(R - 1) + g(R)$의 값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 양의 정수 $L,ドル $R$이 공백으로 구분되어 주어진다. $(1 \le L \le R \le 100,000円)$

출력

$g(L) + g(L + 1) + g(L + 2) + \cdots + g(R - 1) + g(R)$을 출력한다.

제한

힌트