小约翰喜欢回文数，并认为它们是“公平的”（这是一个形容美好的花哨词汇）。回文数是指一个从左向右读和从右向左读都一样的整数——例如 6、11 和 121 都是回文数，而 10、12、223 和 2244 则不是（尽管 010=10，但在判断一个数是否为回文数时，我们不考虑前导零）。

他最近也对平方数产生了兴趣，并定义了公平且平方（fair and square）数——它是一个同时满足是回文数且是某个回文数的平方的数。例如，1、9 和 121 是公平且平方数（它们分别是 1、3 和 11 的平方，且这些底数本身也是回文数），而 16、22 和 676 则不是公平且平方数：16 不是回文数，22 不是平方数，而 676 虽然是回文数且是平方数，但它是 26 的平方，而 26 不是回文数。

现在他想寻找更大的公平且平方数。你的任务是，给定一个小约翰正在搜索的区间，告诉他该区间内有多少个公平且平方数，以便他知道何时找全了它们。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来有 $T$ 行，每行包含两个整数 $A$ 和 $B$，表示小约翰正在查看的区间的端点。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是大于或等于 $A$ 且小于或等于 $B$ 的公平且平方数的数量。

数据范围

小数据集（测试集 1 - 可见；10 分）

$1 \le T \le 100$。 $1 \le A \le B \le 1000$。

第一个大数据集（测试集 2 - 隐藏；35 分）

$1 \le T \le 10000$。 $1 \le A \le B \le 10^{14}$。

第二个大数据集（测试集 3 - 隐藏；55 分）

$1 \le T \le 1000$。 $1 \le A \le B \le 10^{100}$。

样例

样例输入 1

3
1 4
10 120
100 1000

样例输出 1

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