Description

彩票系统正在改革！过去的彩票系统使用一台机器生成一个随机中奖号码。但由于作弊问题频发，如今彩票系统决定增加第二台机器。新的中奖号码将由这两台机器各自生成的随机数，进行按位与（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 想知道共有多少种不同的方式，两台机器生成的数对能够使她中奖。

你能帮助她计算出这个数量吗？

Input Format

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

Output Format

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

5
3 4 2
4 5 2
7 8 5
45 56 35
103 143 88

Case #1: 10
Case #2: 16
Case #3: 52
Case #4: 2411
Case #5: 14377

Hint

样例解释

以第一个测试用例为例，以下是可能由两台机器生成的、使 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 完成。