아홉 없는 수

아홉 없는 수는 지루할 때 해 볼 수 있는 수 세기 게임이다. 이 게임에서는 올바른 수만 말할 수 있다. 다음 조건이 모두 참일 때, 그리고 그럴 때에만 어떤 수가 올바르다:

• 자연수이다(즉, 집합 {1, 2, 3...}에 속한다)

• 밑이 10인 표현의 어느 위치에도 숫자 9가 포함되지 않는다

• 9로 나누어떨어지지 않는다

예를 들어, 수 16와 17는 올바르다. 수 18, 19, 17.2, 그리고 -17는 올바르지 않다.

게임의 첫 차례에는 올바른 수 F를 선택해 말한다. 이후 각 차례에는 그다음 올바른 수를 말한다. 예를 들어, F = 16로 게임을 시작했다면 16, 17, 20, 21 등을 차례로 말하게 된다.

Alice는 이 게임을 매우 잘하며 절대 실수하지 않는다. Alice는 첫 수가 F이고 마지막 수가 L인 게임을 했다는 것을 기억한다(게임에 지쳐서 그만두었을 때의 수가 마지막 수이다). Alice는 게임이 총 몇 차례 동안 진행되었는지(즉, 자신이 몇 개의 수를 말했는지) 궁금해한다.

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 60초. 메모리 제한: 1 GB. F에는 숫자 9가 포함되지 않는다. F는 9로 나누어떨어지지 않는다. L에는 숫자 9가 포함되지 않는다. L은 9로 나누어떨어지지 않는다.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ F < L ≤ $10^{6}$.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ F < L ≤ $10^{18}$.

입력은 정수 T 하나가 포함된 한 줄로 시작하며, 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 위에서 설명한 게임의 첫 수와 마지막 수인 두 정수 F와 L이 포함된 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y이 포함된 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y은 게임이 진행된 차례의 수이다.

예제 케이스 #1에서 게임은 9차례 동안 진행되었으며, Alice가 말한 수는 다음과 같다: 16, 17, 20, 21, 22, 23, 24, 25, 26.

예제 케이스 #2에서 게임은 4차례 동안 진행되었으며, Alice가 말한 수는 다음과 같다: 88, 100, 101, 102.