흥미로운 구간 (작은 입력)

양의 정수를 앞자리 0 없이 십진법으로 적었을 때 앞에서 읽으나 뒤에서 읽으나 같으면 그 수를 회문수라고 한다. 예를 들어 5, 77, 363, 4884, 11111, 12121, 349943은 모두 회문수다.

정수 구간이 회문수를 짝수 개 포함하면 그 구간을 흥미로운 구간이라고 한다. $L \le R$인 구간 $[L, R]$은 $L$부터 $R$까지의 정수를 차례로 늘어놓은 수열 $(L, L+1, L+2, \dots, R-1, R)$이며, $L$과 $R$은 각각 이 구간의 첫 수와 마지막 수다. 0은 짝수이므로 회문수를 하나도 포함하지 않는 구간도 흥미롭다.

$L \le L_1 \le R_1 \le R$이면 구간 $[L_1, R_1]$을 $[L, R]$의 부분 구간이라고 한다. $[L, R]$의 부분 구간 가운데 흥미로운 것이 몇 개인지 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 각 테스트 케이스가 하나씩 주어진다. 각 줄에는 두 양의 정수 $L$과 $R$이 이 순서로 공백 하나를 사이에 두고 주어진다.

제한

• $1 \le T \le 120$
• $1 \le L \le R \le 10^{13}$

각 테스트 케이스마다 한 줄씩 Case #x: y 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 $[L, R]$의 흥미로운 부분 구간의 개수를 $1000000007$로 나눈 나머지다.