흥미로운 구간

양의 정수는 그 십진법 표기(앞에 오는 영이 없는 표기)가 회문 문자열(앞에서 읽으나 뒤에서 읽으나 같은 문자열)이면 회문수이다. 예를 들어 수 5, 77, 363, 4884, 11111, 12121, 349943은 회문수이다.

정수 구간은 회문수를 짝수 개 포함하면 흥미롭다. L ≤ R인 구간 [L, R]은 L부터 R까지의 정수들을 양 끝을 포함하여 나열한 수열 (L, L+1, L+2, ..., R-1, R)로 정의된다. L과 R은 각각 구간의 처음 수와 마지막 수이다.

L ≤ $L_{1}$ ≤ $R_{1}$ ≤ R이면 구간 $[L_{1},R_{1}]$은 [L,R]의 부분 구간이다. 주어진 [L,R]에 흥미로운 부분 구간이 몇 개 있는지 구한다.

제한

테스트 세트당 시간 제한: 45초. 메모리 제한: 1 GB.

1 ≤ T ≤ 120

작은 데이터 세트

1 ≤ L ≤ R ≤ $10^{13}$

큰 데이터 세트

1 ≤ L ≤ R ≤ $10^{100}$

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 공백으로 구분된 두 양의 정수 L과 R이 이 순서대로 주어지는 한 줄로 이루어진다.

각 테스트 케이스마다 한 줄을 출력한다. 그 줄에는 "Case #x: y"을 출력한다. 여기서 x는 1부터 시작하는 케이스 번호이고, y는 [L,R]의 흥미로운 부분 구간 수를 1000000007로 나눈 나머지이다.