Problem D: Differentiate the polynomials![Medium]

Problem D: Differentiate the polynomials![Medium]

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1087  Solved: 180
[Submit][Status][Web Board]

Description

Joy is now working on a project including bunches of mathematical problems. However, as you know, Joy is not good at math.(You can assume he is not good at everything) He wants a program to calculate the differentiate of polynomials.

Input


The first line includes a positive integer T (T<=100) representing the number of test cases.

The second line includes an integer n representing the number of terms of the polynomial. 

Then in the next n lines, each line includes the coefficients and exponents of the each term. (0 < n<= 1000, all exponents are in the range [-1000, 1000], all coefficients are in the range [-1000, 1000])


Output

For each test case, print the polynomial in ascending order of each exponents. If several terms have same exponent, you should add them up. Remember to pay attention to the format of the polynomial.

Sample Input

2
2
1 2
2 3
2
1 -2
-2 3

Sample Output

2x+6x^2
-2x^-3-6x^2

HINT

[Submit][Status]