흥미로운 정수

각 자릿수의 곱이 각 자릿수의 합으로 나누어떨어지는 정수를 흥미로운 정수라고 하자. 두 정수 $\mathbf{A}$과 $\mathbf{B}$이 주어진다. $\mathbf{A}$ 이상 $\mathbf{B}$ 이하인 흥미로운 정수의 개수를 구한다.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$.

테스트 세트 1

$1 \le \mathbf{A} \le \mathbf{B} \le 10^5$.

테스트 세트 2

$1 \le \mathbf{A} \le \mathbf{B} \le 10^{12}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다.

각 줄은 하나의 테스트 케이스를 나타내며 두 정수 $\mathbf{A}$와 $\mathbf{B}$를 포함한다.

각 테스트 케이스마다 Case #$x$: $y$을 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며 1부터 시작하고, $y$는 $\mathbf{A}$ 이상 $\mathbf{B}$ 이하인 흥미로운 정수의 개수이다.

예제 케이스 #1에서는 한 자리 정수의 경우 자릿수의 곱과 자릿수의 합이 같으므로, $1$ 이상 $9$ 이하인 모든 정수가 흥미로운 정수이다.

예제 케이스 #2에서는 $91$ 이상 $99$ 이하인 흥미로운 정수가 없다.

예제 케이스 #3에서는 $451$ 이상 $460$ 이하인 흥미로운 정수가 다섯 개 있다:

• $451$ (자릿수의 곱은 $4 \times 5 \times 1 = 20$, 자릿수의 합은 $4 + 5 + 1 = 10$이다).

• $453$ (자릿수의 곱은 $4 \times 5 \times 3 = 60$, 자릿수의 합은 $4 + 5 + 3 = 12$이다).

• $456$ (자릿수의 곱은 $4 \times 5 \times 6 = 120$, 자릿수의 합은 $4 + 5 + 6 = 15$이다).

• $459$ (자릿수의 곱은 $4 \times 5 \times 9 = 180$, 자릿수의 합은 $4 + 5 + 9 = 18$이다).

• $460$ (자릿수의 곱은 $4 \times 6 \times 0 = 0$, 자릿수의 합은 $4 + 6 + 0 = 10$이다).

.