熊猫先生喜欢玩数字。有一天，他拿到了数字 3612，并发现它很有趣。3612 可以被拆分为 3 个数字 3、6 和 12，它们构成了一个整数等比数列。

整数等比数列是指一个至少包含 3 个正整数的序列 $a_0, a_1, \dots, a_{n-1}$，且存在一个正数 $D$ ($D > 1$)，使得对于每个 $i(0 \le i < n - 1)$，都有 $a_i \times D = a_{i+1}$。

熊猫先生将这类数字称为“快乐数字”。他还宣布禁止前导零，这意味着数字前不能有多余的零。现在，熊猫先生想知道在 $L$ 和 $R$ 之间（包含 $L$ 和 $R$）有多少个快乐数字。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例包含一行，由两个数字 $L$ 和 $R$ 组成。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 $L$ 和 $R$ 之间（包含 $L$ 和 $R$）的快乐数字个数。

数据范围

• $1 \le T \le 2 \times 10^5$
• $0 \le L \le R \le 10^{15}$

样例

输入格式 1

4
123 124
468 470
248 248
124816 124832

输出格式 1

Case #1: 1
Case #2: 1
Case #3: 1
Case #4: 1

说明

在第一个测试用例中，123 到 124 之间唯一的快乐数字是 124，其中 $1 \times 2 = 2$ 且 $2 \times 2 = 4$。

在第二个测试用例中，唯一的快乐数字是 248。

在第三个测试用例中，唯一的快乐数字是 469，公比为 $3/2$。

在第四个测试用例中，124816 到 124832 之间唯一的快乐数字是 124816，其中 $1 \times 2 = 2$，$2 \times 2 = 4$，$4 \times 2 = 8$ 且 $8 \times 2 = 16$。