题目描述

Ron 读了一本关于无聊数的书。根据这本书，一个正整数被称为无聊数，如果它所有偶数位上的数字都是偶数，且所有奇数位上的数字都是奇数。数字的位数从左到右从 $1$ 开始编号。例如，数字 $1478$ 是无聊数，因为奇数位上的数字为 $\{1, 7\}$ 均为奇数，偶数位上的数字为 $\{4, 8\}$ 均为偶数。

给定两个数 $L$ 和 $R$，Ron 想要统计区间 $[L, R]$（包含 $L$ 和 $R$）内有多少个无聊数。Ron 无法解决这个问题，因此他需要你的帮助。

输入格式

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

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是无聊数的个数。

3
5 15
120 125
779 783

Case #1: 6
Case #2: 3
Case #3: 2

提示

在样例 #1 中，区间内的数字为 $\{5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15\}$，其中 $\{5, 7, 9, 10, 12, 14\}$ 是无聊数，因此答案为 $6$。

在样例 #2 中，区间内的数字为 $\{120, 121, 122, 123, 124, 125\}$，其中 $\{121, 123, 125\}$ 是无聊数，因此答案为 $3$。

在样例 #3 中，区间内的数字为 $\{779, 780, 781, 782, 783\}$，其中 $\{781, 783\}$ 是无聊数，因此答案为 $2$。

限制条件

$1 \le T \le 100$。

测试集 1

$1 \le L \le R \le 10^3$。

测试集 2

$1 \le L \le R \le 10^{18}$。

翻译由 DeepSeek V4 Pro 完成