P13251 [GCJ 2014 #1B] New Lottery Game

彩票系统正在改革！过去的彩票系统使用一台机器生成一个随机中奖号码。但由于作弊问题频发，如今彩票系统决定增加第二台机器。新的中奖号码将由这两台机器各自生成的随机数，进行按位与（bitwise AND）运算后得到。 要计算 $X$ 和 $Y$ 的按位与操作，将它们都转换为二进制表示；结果中每一位是 $1$ 的前提是，$X$ 和 $Y$ 的对应位都为 $1$，否则为 $0$。在大多数编程语言中，$X$ 和 $Y$ 的按位与操作写作 $X \& Y$。 例如： - 旧机器生成的数字是 $7 = 0111$； - 新机器生成的数字是 $11 = 1011$； - 则中奖号码为 $(7 \text{ AND } 11) = (0111 \text{ AND } 1011) = 0011 = 3$。 通过这一改革，彩票公司期望能够减少虚假兑奖的情况。但不幸的是，该公司的一名员工泄露了以下信息：旧机器生成的随机数始终小于 $A$，而新机器生成的随机数始终小于 $B$。 Catalina 想赢得这次彩票。她打算购买所有小于 $K$ 的非负整数。 现在，给定 $A$、$B$ 和 $K$，Catalina 想知道共有多少种不同的方式，两台机器生成的数对能够使她中奖。 你能帮助她计算出这个数量吗？

输入的第一行是测试用例的数量 $T$。接下来 $T$ 行，每行包含三个整数 $A$、$B$ 和 $K$。

对于每个测试用例，输出一行 `"Case #x: y"`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是两台机器能生成使 Catalina 获胜的数对总数。

**样例解释** 以第一个测试用例为例，以下是可能由两台机器生成的、使 Catalina 获胜的 10 个数对（分别由旧机器和新机器生成）： $\langle 0,0\rangle,\ \langle 0,1\rangle,\ \langle 0,2\rangle,\ \langle 0,3\rangle,\ \langle 1,0\rangle,$ $\langle 1,1\rangle,\ \langle 1,2\rangle,\ \langle 1,3\rangle,\ \langle 2,0\rangle,\ \langle 2,1\rangle$ 请注意，$\langle 0,1\rangle$ 与 $\langle 1,0\rangle$ 是不同的数对。 另外，虽然机器可能生成 $\langle 2,2\rangle$，但该数对不会使 Catalina 获胜，因为 $(2 \text{ AND } 2) = 2$，而她只购买了 $0$ 和 $1$。 ## 限制条件 - $1 \leq T \leq 100$ **小数据集（8 分）** - 时间限制：~~60~~ 3 秒 - $1 \leq A \leq 1000$ - $1 \leq B \leq 1000$ - $1 \leq K \leq 1000$ **大数据集（24 分）** - 时间限制：~~120~~ 5 秒 - $1 \leq A \leq 10^9$ - $1 \leq B \leq 10^9$ - $1 \leq K \leq 10^9$ 翻译由 ChatGPT-4o 完成。