HARANGES - F - Interesting Ranges

A positive integer is a palindrome if its decimal representation (without leading zeros) is a palindromic string (a string that reads the same forwards and backwards). For example, the numbers 5, 77, 363, 4884, 11111, 12121 and 349943 are palindromes.

A range of integers is interesting if it contains an even number of palindromes. The range [L, R], with L ≤ R, is defined as the sequence of integers from L to R (inclusive): (L, L+1, L+2, ... R-1, R). L and R are the range's first and last numbers.

The range [L1, R1] is a subrange of [L, R] if L ≤ L1 ≤ R1 ≤ R. Your job is to determine how many interesting subranges of [L, R] there are.

Input

The first line of input gives the number of test cases, T. T test cases follow. Each test case is a single line containing two positive integers, L and R (in that order), separated by a space.

Output

For each test case, output one line. That line should contain "Case #x: y", where x is the case number starting with 1, and y is the number of interesting subranges of [L, R], modulo 1000000007.

Limits

1 ≤ T ≤ 120

Small dataset: 1 ≤ LR ≤ 1013

Large dataset; 1 ≤ LR ≤ 10100

Sample

Input:
3
1 2
1 7
12 110

Output:
Case #1: 1
Case #2: 12
Case #3: 2466

Added by:Alvaro Javier Medina Balboa
Date:2010-10-15
Time limit:1.666s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.