题目描述

The Lottery is changing! The Lottery used to have a machine to generate a random winning number. But due to cheating problems, the Lottery has decided to add another machine. The new winning number will be the result of the bitwise-AND operation between the two random numbers generated by the two machines.

To find the bitwise-AND of $X$ and $Y$, write them both in binary; then a bit in the result in binary has a $1$ if the corresponding bits of $X$ and $Y$ were both $1$, and a $0$ otherwise. In most programming languages, the bitwise-AND of $X$ and $Y$ is written $X \& Y$.

For example:

• The old machine generates the number $7 = 0111$.
• The new machine generates the number $11 = 1011$.
• The winning number will be $(7 \text{ AND } 11) = (0111 \text{ AND } 1011) = 0011 = 3$.

With this measure, the Lottery expects to reduce the cases of fraudulent claims, but unfortunately an employee from the Lottery company has leaked the following information: the old machine will always generate a non-negative integer less than $A$ and the new one will always generate a non-negative integer less than $B$.

Catalina wants to win this lottery and to give it a try she decided to buy all non-negative integers less than $K$.

Given $A$, $B$ and $K$, Catalina would like to know in how many different ways the machines can generate a pair of numbers that will make her a winner.

Could you help her?

输入格式

The first line of the input gives the number of test cases, $T$. $T$ lines follow, each line with three numbers $A$ $B$ $K$.

输出格式

For each test case, output one line containing "Case #$x$: $y$", where $x$ is the test case number (starting from $1$) and $y$ is the number of possible pairs that the machines can generate to make Catalina a winner.

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

提示

Sample Explanation

In the first test case, these are the 10 possible pairs generated by the old and new machine respectively that will make her a winner: $\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$ and $\langle 2,1\rangle$. Notice that $\langle 0,1\rangle$ is not the same as $\langle 1,0\rangle$. Also, although the pair $\langle 2, 2\rangle$ could be generated by the machines it wouldn't make Catalina win since $(2 \text{ AND } 2) = 2$ and she only bought the numbers $0$ and $1$.

Limits

• $1 \leq T \leq 100$.

Small dataset(8 Pts)

• Time limit: 60 3 seconds.
• $1 \leq A \leq 1000$.
• $1 \leq B \leq 1000$.
• $1 \leq K \leq 1000$.

Large dataset(24 Pts)

• Time limit: 120 5 seconds.
• $1 \leq A \leq 10^9$.
• $1 \leq B \leq 10^9$.
• $1 \leq K \leq 10^9$.