彩票系统正在进行改革！过去，彩票系统使用一台机器来生成一个随机的中奖号码。但由于存在作弊问题，彩票公司决定增加另一台机器。新的中奖号码将是两台机器生成的随机数进行按位与（bitwise-AND）运算的结果。

要计算 $X$ 和 $Y$ 的按位与，需将它们写成二进制形式；如果 $X$ 和 $Y$ 对应位上的数字均为 1，则结果的对应位为 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 中奖的机器生成数对的数量。

样例

输入格式 1

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

输出格式 1

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

说明

在第一个测试用例中，以下是旧机器和新机器分别生成的 10 种能让她中奖的数对：<0,0>、<0,1>、<0,2>、<0,3>、<1,0>、<1,1>、<1,2>、<1,3>、<2,0> 和 <2,1>。注意 <0,1> 与 <1,0> 不同。此外，尽管数对 <2, 2> 可以由机器生成，但它不会让 Catalina 中奖，因为 $(2 \text{ AND } 2) = 2$，而她只购买了 0 和 1。