## UCI2009B - Binomial Coefficients

We all got too excited when we learned (A + B)^2 = A^2 + 2AB + B^2. After solving this problem, maybe you could get even more excited because you will have to calculate (A + B)^N, where (0 <= N <= 1000).

1. Consecutive terms must be separated by a '+' character.
2. At the i-th term, A must be raised to N - i and B must be raised to i (0<=i<=N).
3. Binomial coefficients must not be printed, print their prime factorization instead.
4. Use '^' for exponentiation and 'x' for multiplication in step 3.
5. Avoid the use of number 1 when possible.

See sample output for clarification.

### Input

Input starts with an integer T, representing the number of test cases (1<=T<=15). T lines follow, each one consisting of an integer N, (0<=N<=1000).

### Output

For each test case, print (A + B)^N, on a single line.

### Example

`Input:6012345Output:1A+BA^2+2xAB+B^2A^3+3xA^2B+3xAB^2+B^3A^4+2^2xA^3B+2x3xA^2B^2+2^2xAB^3+B^4A^5+5xA^4B+2x5xA^3B^2+2x5xA^2B^3+5xAB^4+B^5Warning: Large output. Be careful with certain languages.` nadstratosfer: 2019-11-26 06:35:55 Output for (A+B)^1000 is 340+KB. How about, instead of advising "being careful", set the TL appropriately? In fact, I only got an elegant PyPy solution accepted because I took advantage of certain undefined behaviour. No amount of care will make up for unreasonable TL. Parul Yadav: 2015-08-11 07:39:02 my 100th Bharath Reddy: 2013-06-13 12:50:22 Not so hard... Inspiron: 2013-02-20 08:20:21 ... Last edit: 2013-05-25 02:02:48 saket diwakar: 2013-01-27 21:55:08 very painful to code it..bt never mind...:) Last edit: 2013-01-30 21:50:14 Ajey Golsangi: 2011-12-06 05:58:32 Painful to code the solution.