题目描述

Alice 和 Bob 正在玩一款新的虚拟现实团队游戏——街道检查员。游戏设定在一条极长的街道上，街道被划分为从 $0$ 到 $10^9$（包含两端）的格子。游戏开始时，Alice 和 Bob 站在编号为 $0$ 的格子上，并获得一个在区间 $[L, R]$（包含两端）内随机生成的数 $X$。Alice 只能跳到编号为奇数的格子，而 Bob 只能跳到编号为偶数的格子。如果格子上的数字能整除 $X$，那么落在该格子上的玩家必须用自己最喜欢的颜色涂色。当格子 $X$ 被涂色后游戏结束。

如果两人涂色的格子数量之差的绝对值不超过 $2$，则双方都认为游戏是 有趣的。请帮助 Alice 和 Bob 找出区间 $[L, R]$ 中有多少个数可能使得游戏变得有趣。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来 $T$ 行，每行包含两个整数 $L$ 和 $R$，表示用于生成随机数 $X$ 的区间的起点和终点。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是区间 $[L, R]$ 中能使游戏变得有趣的数字个数。

2
5 10
102 102

Case #1: 5
Case #2: 1

提示

对于第一个样例，我们考察区间 $[5, 10]$ 中的所有数字：

• $5$：Alice 会涂色 $2$ 个格子：$\{1, 5\}$，Bob 不会涂任何格子。绝对值差为 $2$，游戏有趣。
• $6$：Alice 涂色 $2$ 个格子：$\{1, 3\}$，Bob 涂色 $2$ 个格子：$\{2, 6\}$。绝对值差为 $0$，游戏有趣。
• $7$：Alice 涂色 $2$ 个格子：$\{1, 7\}$，Bob 涂色 $0$ 个格子。绝对值差为 $2$，游戏有趣。
• $8$：Alice 涂色 $1$ 个格子：$\{1\}$，Bob 涂色 $3$ 个格子：$\{2, 4, 8\}$。绝对值差为 $2$，游戏有趣。
• $9$：Alice 涂色 $3$ 个格子：$\{1, 3, 9\}$，Bob 涂色 $0$ 个格子。绝对值差为 $3 > 2$，游戏无趣。
• $10$：Alice 涂色 $2$ 个格子：$\{1, 5\}$，Bob 涂色 $2$ 个格子：$\{2, 10\}$。绝对值差为 $0$，游戏有趣。

因此答案为 $5$。

在第二个样例中，只有一个数字 $102$。Alice 涂色 $4$ 个格子：$\{1, 3, 17, 51\}$，Bob 涂色 $4$ 个格子：$\{2, 6, 34, 102\}$。绝对值差为 $0$，游戏有趣。

限制条件

$1 \le T \le 100$。

$0 \le R - L \le 10^5$。

测试集 1（可见）

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

测试集 2（隐藏）

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

翻译由 DeepSeek V4 Pro 完成