New Lottery Game (Large)

The lottery is changing. It used to draw the winning number with a single machine, but after repeated cheating the lottery company 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 of them in binary. A bit of the result is 1 when the matching bits of $X$ and $Y$ are both 1, and 0 otherwise. Most programming languages write this operation as X & Y.

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

An employee of the lottery company leaked one more fact: the old machine always draws a non-negative integer smaller than $A$, and the new machine always draws a non-negative integer smaller than $B$.

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

You are given $A$, $B$ and $K$. Count the pairs of numbers the two machines can draw 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 10^9$
• $1 \le B \le 10^9$
• $1 \le K \le 10^9$

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 two machines can draw that make Catalina a winner.

Take $A = 3$, $B = 4$, $K = 2$. Ten pairs make Catalina win: (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0) and (2, 1). The first number is the draw of the old machine and the second one is the draw of the new machine, so (0, 1) and (1, 0) are different pairs. The machines can also draw (2, 2), but (2 AND 2) = 2 and Catalina bought only 0 and 1, so that pair does not win.