Description

Little John 喜欢回文数，并认为它们是公平的（fair，意思就是“美好”）。一个 $palindrome$（回文数）是指这样一个整数：它正着读和反着读都一样——比如 $6$、$11$ 和 $121$ 都是回文数，而 $10$、$12$、$223$ 和 $2244$ 则不是（即使 $010 = 10$，我们在判断回文数时不考虑前导零）。

最近他对平方数也产生了兴趣，并给出了 $fair$ $and$ $square$ 数的定义——即同时满足以下两个条件的数：

• 它是一个回文数；
• 它本身也是某个回文数的平方。

例如，$1$、$9$ 和 $121$ 都是 fair and square 数（它们分别是 $1$、$3$ 和 $11$ 的平方，且自身也都是回文数），而 $16$、$22$ 和 $676$ 都不是 fair and square 数：$16$ 不是回文数，$22$ 不是平方数，$676$ 虽然既是回文数又是平方数，但它是 $26$ 的平方，而 $26$ 不是回文数。

现在他想寻找更大的 fair and square 数。你的任务是：给定 Little John 要查找的区间，告诉他该区间内有多少个 fair and square 数，这样他就知道自己是否已经找到全部了。

通常，Google Code Jam 的题目会有 1 个 Small 输入和 1 个 Large 输入。本题有 1 个 Small 输入和 2 个 Large 输入。当你通过 Small 输入后，就可以下载任意一个 Large 输入。像往常一样，你可以多次尝试 Small 输入（每次错误会有时间惩罚），而每个 Large 输入只有一次提交机会。

Input Format

输入的第一行为测试用例数量 $T$。接下来 $T$ 行，每行包含两个整数 $A$ 和 $B$，表示 Little John 关注的区间的两个端点。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 表示测试用例编号（从 $1$ 开始），$y$ 表示区间 $[A, B]$ 内 fair and square 数的个数（包括 $A$ 和 $B$）。

3
1 4
10 120
100 1000

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

Hint

限制条件

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

• $1 \leq T \leq 100$
• $1 \leq A \leq B \leq 1000$

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

• $1 \leq T \leq 10000$
• $1 \leq A \leq B \leq 10^{14}$

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

• $1 \leq T \leq 1000$
• $1 \leq A \leq B \leq 10^{100}$

翻译由 ChatGPT-4.1 完成。