재활용된 수

텔레비전에서 같은 것들이 계속해서 반복해서 재활용되는 모습을 보며 짜증이 난 적이 있는가? 개인적으로 나는 텔레비전에 관심이 없지만, 가끔 수를 보며 그런 기분을 느낀다.

서로 다른 양의 정수의 순서쌍 (n, m)에 대해, n의 뒤쪽에서 일부 자릿수를 순서를 바꾸지 않고 앞쪽으로 옮겨 m을 얻을 수 있다면 이 순서쌍을 재활용된 순서쌍이라고 하자. 예를 들어, (12345, 34512)은 재활용된 순서쌍이다. 12345의 끝에서 345을 앞쪽으로 옮기면 34512을 얻을 수 있기 때문이다. 재활용된 순서쌍이 되려면 n과 m의 자릿수가 같아야 한다는 점에 유의하라. n과 m 모두 앞에 영이 올 수 없다.

자릿수가 같고 앞에 영이 없는 정수 A와 B가 주어질 때, A ≤ n < m ≤ B를 만족하는 서로 다른 재활용된 순서쌍 (n, m)은 몇 개인가?

제한

메모리 제한: 1GB. 시간 제한: 테스트 세트당 30초. 1 ≤ T ≤ 50. A와 B의 자릿수는 같다.

테스트 세트 1 (결과 공개)

1 ≤ A ≤ B ≤ 1000.

테스트 세트 2 (결과 비공개)

1 ≤ A ≤ B ≤ 2000000.

입력의 첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 정수 A와 B가 포함된 한 줄로 이루어진다.

각 테스트 케이스마다 "Case #x: y"가 포함된 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 A ≤ n < m ≤ B를 만족하는 재활용된 순서쌍 (n, m)의 개수이다.

Case #4의 출력이 정말 확실한가?

그렇다. Case #4의 출력은 확실하다.