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 and , write them both in binary; then a bit in the result in binary has a if the corresponding bits of and were both , and a otherwise. In most programming languages, the bitwise-AND of and is written .
For example:
The old machine generates the number .
The new machine generates the number .
The winning number will be .
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 and the new one will always generate a non-negative integer less than .
Catalina wants to win this lottery and to give it a try she decided to buy all non-negative integers less than .
Given , and , 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, . lines follow, each line with three numbers .
输出格式
For each test case, output one line containing "Case #: ", where is the test case number (starting from ) and is the number of possible pairs that the machines can generate to make Catalina a winner.
样例
样例输入 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
数据范围与提示
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: , and . Notice that is not the same as . Also, although the pair could be generated by the machines it wouldn't make Catalina win since and she only bought the numbers and .
