P16737 [GKS 2019 #E] Street Checkers

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]$ 中能使游戏变得有趣的数字个数。

对于第一个样例，我们考察区间 $[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 完成