E  — Binomial Theorem

Time Limit: 1 sec
Memory Limit: 32 MB

John likes mathematics a lot. His main passion is the binomial theorem. However it is rather hard to calculate binomial coefficients, so he decided to write a computer program that can expand any power of a sum into a sum of powers. Mathematically it can be written like this:
(a+b)^k = x₁a^k + x₂a^k−1b + x₃a^k−2b² + … + x_k+1b^k
where x_{1 … k+1} are binomial coefficients x_i = C_kⁱ .

INPUT

There is a number of tests T (T ≤ 100) on the first line. After T test follows. Each test is written on a single line in form of (a+b)^k. Where a and b are same variables names. Variables names are strings constructed from ’a’–’z’ characters. And k (1 ≤ k ≤ 50) is a power that you need to raise the sum. You can assume that there are no lines longer than 100 characters.

OUTPUT

For each test output a single line "Case N: T". Where N is the test number (starting from 1) and T is an expanded expression (see examples for clarification). By the way, you shouldn’t output coefficients and powers equal to one.

SAMPLE INPUT

3
(a+b)^1
(alpha+omega)^2
(acm+icpc)^3

SAMPLE OUTPUT

Case 1: a+b
Case 2: alpha^2+2*alpha*omega+omega^2
Case 3: acm^3+3*acm^2*icpc+3*acm*icpc^2+icpc^3