Representación de Polinomios

Teniendo en cuenta los coeficientes de un polinomio de grado 0 a 8, usted tiene la tarea de formatear el polinomio en un formato legible con los caracteres innecesarios quitados. Por ejemplo, dados los coeficientes 0, 0, 0, 1, 21, -331, 0, 1 y -1, se debe generar una línea de salida que muestra x^5 + 21x^4 - 331 x^3 + x - 1.

Las reglas para formatear son las siguientes:

• Los términos deben aparecer en orden de grado decreciente.
• Los exponentes deben aparecer después de un acento circunflejo, ^.
• Sólo deben aparecer términos con coeficientes distintos de cero, a menos que todos los términos cuenten con coeficientes cero, en cuyo caso debería aparecer sólo el término independiente.
• Debe colocarse un espacio a ambos lados de las operaciones binarias + y -.
• Si el término de mayor grado con coeficiente distinto de cero es positivo, entonces ningún signo debe precederle. Un término negativo debe ser precedido por un signo menos (sin ningún espacio), como por ejemplo en el polinomio -7x^2 + 30x + 66
• Los coeficientes 1 y -1 deben aparecer sólo cuando se trata de los términos independientes. Es decir, en lugar de -1x^3 + 1 x^2 + 3x^1 - 1, la salida debería aparecer como -x^3 + x^2 + 3x - 1.

Entrada

La primera línea contiene un entero indicando el número de casos de prueba. Cada siguiente línea corresponde a un caso de prueba conteniendo nueve coeficientes delimitados por uno o más espacios. Cada coeficiente es un número entero con una magnitud de menor de 1000.

Salida

La salida consiste en una línea por cada línea de coeficientes de entrada. Esta línea debe mostrar un polinomio formateado.

Ejemplo de Entrada

2
0 0 0 1 21 -331 0 1 -1
0 0 0 0 0 0 -54 5 0

Ejemplo de Salida

x^5 + 21x^4 - 331x^3 + x - 1
-54x^2 + 5x