흥미로운 구간

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

$L \le R$인 두 정수에 대해 구간 $[L, R]$은 $L$부터 $R$까지의 정수를 차례로 늘어놓은 수열 $(L, L+1, L+2, \dots, R-1, R)$을 뜻한다. 구간 안에 있는 팰린드롬의 개수가 짝수이면 그 구간을 흥미로운 구간이라고 한다. 팰린드롬이 하나도 없는 구간도 짝수이므로 흥미로운 구간이다.

$L \le L_1 \le R_1 \le R$이면 구간 $[L_1, R_1]$은 구간 $[L, R]$의 부분 구간이다. $L$과 $R$이 주어질 때 $[L, R]$의 흥미로운 부분 구간이 몇 개인지 구하라.

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

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

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