题目描述

对于一个$n$位的十进制数$x$（$A_n,A_{n-1}\ldots \ldots A_1$），我们定义它的权重为：

$$F(x)=A_n\times 2_{n-1}+A_{n-1}\times 2_{n-2}+\ldots \ldots+A_1\times 2_0 $$

现在，给你两个十进制数$A$和$B$，请计算出在闭区间$[0, B]$之中，有多少个数$x$的权重不大于$A$的权重，即$F(x)\le F(A)$。由于答案可能很大，你只需要输出答案对$1000000007$（$10^9 + 7$）取模的结果即可。

输入格式

第一行一个正整数$T$，表示测例的个数。

随后$T$行，每行描述一个测例，包含两个非负整数$A,B$，之间用空格隔开。含义见问题描述。

输出格式

对于每个测例，单独输出一行Case #t: ans，其中t表示测例编号，从$1$开始递增，ans表示该组测例的答案（对$1000000007$取模后的结果）。

样例

3
0 100
1 10
5 100

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

样例说明

对于Case #3，符合条件的数有$0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 20, 21, 100$，共$13$个。

样例描述有修改，请注意！

数据规模及约定

对于$20\%$的数据，$A, B \le 10^9$；

对于$30\%$的数据，$A, B \le 10^{18}$；

对于$100\%$的数据，$A,B \le 10^{200}，T\le 5$。