Migrated from Lutece 428 Mountain Number

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

A Mountain number is defined as continuous digits {$D_0, D_1\cdots D_{n-1}$} ($D_0 > 0$ and $n \geq 3$),which exist $D_m$ ($0 < m < n - 1$) satisfied $D_{i-1} < D_i$ ($0 < i\leq m$) and $D_i > D_{i+1}$ ($m\leq i < n - 1$).Such as $121$, $12341$ and so on.

Now,BlinKer is facing a problem.He wants to calculate the number of mountain numbers in the closed interva $[A,B]$. Could you help him?

Input

First line is a integer $T$ ,which means the number of test cases.

Each case has two integers $A,B$ ($0\leq A\leq B<2^{63}$) in a single line.

Output

For each case,first output Case #x: ($x$ start from $1$),then output a single num which is the answer.

Samples

3
121 121
100 101
12341 12344

Case #1: 1
Case #2: 0
Case #3: 3

Resources

2011 UESTC ACM Training for Dynamic Programming