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 =x1ak +x2ak−1b+x3ak−2b2 +...+xk+1bk where x1...k+1 are binomial coefficients xi = Cki . 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+2alphaomega+omega^2 Case 3: acm^3+3acm^2icpc+3acmicpc^2+icpc^3