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.