Your task is to implement polynomial addition after getting two polynomial expression as singly linked list and get the result of polynomial addition as output singly linked list. Read the polynomial until user enters 'y' in the order coefficient and exponential power.

Input:

• The First line of the input contains an integer N denoting the number of test cases.
• Then for each line get coefficient, exponential power, (y/n) 'n': means get the next term of the polynomial, 'y':means get the next polynomial or stop reading the polynomial expression

Constraints

• 1 <= N <= 20

Sample Input:

    1
    2
    3
    n
    4
    2
    n
    1
    1
    n
    4
    0
    y
    5
    3
    n
    3
    2
    n
    2
    1
    n
    1
    0
    y

Sample Output:

    2x^3 + 4x^2 + 1x^1 + 4
    5x^3 + 3x^2 + 2x^1 + 1
    7x^3 + 7x^2 + 3x^1 + 5