Unique String

There are 3 types of letters available. They are A, B and C. You are given the frequencies of them. You have to make a word with all of them but have to maintain one condition that letter A and B will not be adjacent to each other. How many different words you can make maintaining the condition.

For example, if the frequencies of letter A, B and C are 1, 1 and 2, the answer will be 6. The words are ACCB, ACBC, CACB, BCAC, BCCA and CBCA.

Input

First line of input contains the number of test cases T (1<= T <= 100000). Next T lines describe the case. Each case contains three integers x, y and z where x denotes the frequency of A, y denotes the frequency of B and z denotes the frequency of C (0 <= x, y, z <= 100000 && min(x, y) < 3 && (x + y + z) ≥ 1).

Output

For each test case, output a single line contains “Case X: Y” without any quote where X denotes the number of test cases and Y denotes the answer of the problem. Answer could be very large so output the answer modulo 1000000007.

Sample

Input	Output
2 1 1 1 1 1 2	Case 1: 2 Case 2: 6