Migrated from Lutece 822 F(x)

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

For a decimal number $x$ with $n$ digits ($A_{n}A_{n-1}A_{n-2}\cdots A_{2}A_{1}$), we define its weight as $F(x)=A_{n}\times 2^{n-1}+A_{n-1}\times 2^{n-2}+\cdots +A_{2}\times 2+A_{1}\times 1$. Now you are given two numbers $A$ and $B$, please calculate how many numbers are there between $0$ and $B$, inclusive, whose weight is no more than $F(A)$.

Input

The first line has a number $T$ ($T\leq 10000$) , indicating the number of test cases.

For each test case, there are two numbers $A$ and $B$ ($0\leq A,B<10^9$)

Output

For every case,you should output Case #t: at first, without quotes. The $t$ is the case number starting from $1$. Then output the answer.

Samples

3
0 100
1 10
5 100

Case #1: 1
Case #2: 2
Case #3: 13

Resources

2013 ACM/ICPC Asia Regional Chengdu Online