P13251 [GCJ 2014 #1B] New Lottery Game

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.

**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$.