A serious math problem

Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Description

Xiao Jun likes math and he has a serious math question for you to finish.

Define $F[x]$ to the xor sum of all digits of x under the decimal system,for example $F(1234) \ = \ 1 \ xor \ 2 \ xor \ 3 \ xor \ 4 \ = \ 4$.

Two numbers $a, b(a \leq b)$ are given,figure out the answer of $F[a] \ + \ F[a+1] \ + \ F[ a+2]+ \ldots + \ F[ b-2] \ + \ F[ b-1] \ + \ F[b]$ doing a modulo $10^{9}+7$.

Input

The first line of the input is a single integer $T (T < 26)$, indicating the number of testcases.

Then $T$ testcases follow.In each testcase print three lines :

The first line contains one integers $a$.

The second line contains one integers $b$.
$1 \leq |a|, |b| \leq 100001$,$ |a| $ means the length of $a$.

Output

For each test case, output one line "Case #x: y", where $x$ is the case number (starting from 1) and $y$ is the answer.

Sample Input

4 0 1 2 2 1 10 9999 99999

Sample Output

Case #1: 1 Case #2: 2 Case #3: 46 Case #4: 649032

Hint

hujie

Source

BestCoder Round #55 ($)

提交代码