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).

Follow the rules below when giving the answer:

  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:
6
0
1
2
3
4
5

Output:
1
A+B
A^2+2xAB+B^2
A^3+3xA^2B+3xAB^2+B^3
A^4+2^2xA^3B+2x3xA^2B^2+2^2xAB^3+B^4
A^5+5xA^4B+2x5xA^3B^2+2x5xA^2B^3+5xAB^4+B^5

Warning: Large output. Be careful with certain languages.


Added by:Yandry Perez
Date:2009-06-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO

hide comments
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.
2015-08-11 07:39:02 Parul Yadav
my 100th
2013-06-13 12:50:22 Bharath Reddy
Not so hard...
2013-01-27 21:55:08 saket diwakar
very painful to code it..bt never mind...:)

Last edit: 2013-01-30 21:50:14
2011-12-06 05:58:32 Ajey Golsangi
Painful to code the solution.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.