New Lottery Game (Small)

The lottery is changing. It used to have one machine that generated the winning number, but after cheating came to light the lottery added a second machine. The new winning number is the bitwise AND of the two random numbers the two machines produce.

To take the bitwise AND of $X$ and $Y$, write both numbers in binary. A bit of the result is 1 when the corresponding bits of $X$ and $Y$ are both 1, and 0 otherwise. Most programming languages write this operation as X & Y.

For example, if the old machine produces 7 = 0111 and the new machine produces 11 = 1011, the winning number is (0111 AND 1011) = 0011 = 3.

The lottery expected this to cut down on fraudulent claims, but an employee leaked two facts: the old machine always produces a non-negative integer less than $A$, and the new machine always produces a non-negative integer less than $B$.

Catalina wants to win, so she bought every non-negative integer less than $K$.

Given $A$, $B$ and $K$, count the pairs of numbers the two machines can produce that make Catalina a winner.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains three integers $A$, $B$ and $K$, separated by spaces.

Limits

• $1 \le T \le 100$
• $1 \le A \le 1000$
• $1 \le B \le 1000$
• $1 \le K \le 1000$

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the number of pairs the machines can produce that make Catalina a winner.

When $A = 3$, $B = 4$ and $K = 2$, ten pairs make Catalina a winner: (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0) and (2, 1). The first number of a pair comes from the old machine and the second from the new machine, so (0, 1) and (1, 0) are different pairs. The machines can also produce (2, 2), but (2 AND 2) = 2 and Catalina bought only 0 and 1, so that pair does not win.