Description

Loser goddess Lysta want to save the world of Advanced-Mathematic which is facing a serious crisis. She successfully summoned you, a genius warrior, and who are unexceptedly too cautious...What you are doing is not only collecting the equipment as much as you can, but also getting the original skill it to the highest level! So you decide to start from the skill of derivative with a sort of low-level monster, Polynomial, untill the level of derivative get the highest. This is the first step of your great journey, can you get it done perfectly?

Given a polynomial in the simplest form and a positive integer n, output its nth-derivative in the simplest form also.

Format

Input

The first line of input is a positive integer $m(m < 100000)$, represents that there will be $m$ cases following. In following $m$ lines, each line is a case contains a integer $n(0\leq n\leq10)$ and $a$ string $s(length \leq 100)$ which represent the order of the derivative and the polynomial $(order \leq 10)$. We guarantee that each term's factor in polynomial is integer.

Output

Output contains m lines. Each line is a string represrents the result of the nth-derivative in the simplest form.

Samples

3
1 x^2+1
2 2x^3+x^2
5 x^2

2x
12x+2
0

Hints

The simplest form of polynomials means that as the handwritting form of polynomials, permuting every term in the arrangement of desending power, not to write the terms with a factor of 0(except the term is 0), and if the first term's factor is greater than 0, then we don't write the symbol '+', and if a factor is 1 or -1, then we don't write the symbol '1', just tell the property of positive and negative.

Here is some examples: -x+1, x^2-x+2,-x^4-x^2+1, etc.