Многочлены

Снежок нашел листок из старого учебника по математике. На нем перечислены $t$ многочленов от двух переменных.

Теперь Снежок хочет их упростить. Помогите ему.

Во входном файле многочлены записаны в следующем формате:

• Многочлен не содержит пробелов и состоит только из арабских цифр и символов <<n>>, <<m>>, <<+>>, <<->>, <<*>>, <<^>>.

• Многочлен состоит из нескольких слагаемых.

• Если слагаемое входит со знаком минус, то перед ним пишется <<->>.

• Если слагаемое входит со знаком плюс и это не первое слагаемое, то перед ним пишется <<+>>.

• Каждое слагаемое можно представить в виде $a\cdot n^{b}\cdot m^{c}$, где $a$, $b$ и $c$ --- целые неотрицательные числа (если не учитывать знак перед слагаемым), без ведущих нулей, не превышающие $10^5$.

• Слагаемое записывается в следующем формате:

  • Слагаемое является произведением чисел и степеней $n$ и $m$.
  • Назовем числом последовательность подряд идущих цифр, слева и справа от которой стоят не цифры.
  • Перед каждым символом <<^>> находится переменная, то есть символ <<n>> или символ <<m>>.
  • После каждого символа <<^>> находится число.
  • Таким образом, знак <<^>> обозначает, что переменная, стоящая перед ним, возводится в степень числа, стоящего после него. Назовем это множителем.
  • Если после символов <<n>> или <<m>> нет символа <<^ >>, то считается, что эта переменная в этом месте стоит в степени $1$. Назовем каждую такую переменную множителем.
  • Все числа, которые не являются степенями (то есть, те, перед которыми не стоят символы <<^>>), назовем множителями.
  • По обе стороны от каждого символа <<*>> находятся множители.
  • Слагаемое это произведение всех его множителей.
  • Обращаем ваше внимание, что некоторые соседние множители могут не разделяться символом <<*>>.

Для упрощенного многочлена должно выполняться следующее:

• Он записывается в таком же формате, как и исходный.
• Если многочлен тождественно равен нулю, нужно вывести <<0>>.
• Если слагаемое представимо в виде $a \cdot n^b \cdot m^c$, то такое слагаемое должно быть записано как <<an^ bm^ c>>, где на место <<a>>, <<b>> и <<c>> подставлены соответствующие числа.
• Для каждой пары $a$ и $b$ существует не более одного слагаемого, представимого в виде $k\cdot n^a\cdot m^b$.
• Если $n^a\cdot m^b$ входит в многочлен с коэффициентом 0, такое слагаемое писать не надо.
• Если $n^a\cdot m^b$ входит в многочлен с коэффициентом, по модулю равным 1, в таком слагаемом не нужно писать коэффициент.
• В слагаемом вида $a\cdot n^0 \cdot m^c$, переменную <<n>> писать не надо.
• В слагаемом вида $a\cdot n^1 \cdot m^c$, после переменной <<n>> не нужно писать степень.
• Для переменной <<m>> тоже выполняются предыдущие два пункта.
• Слагаемые в многочлене могут идти в любом порядке.

В первой строке задано целое число $t$ --- количество многочленов ($1 \le t \le 100$). В следующих $t$ строках заданы многочлены. Гарантируется, что все числа в них не превосходят $10^5$.

Длины всех строк не превосходят $100$.

Для каждого многочлена выведите его в упрощенном виде.

Гарантируется, что в упрощенном многочлене все числа не превосходят $10^9$.

Пояснение к примеру:

$-n^{2}\*m^{1}+n\*nm3+mn-n+m-n\*m = m-n+2n^{2}m$

$n\*n\*m^{0}m^{2}\*5-m\*2n = -2nm+5n^{2}m^{2}$

$-100n\*m+23+0n^{3} = 23-100nm$

$n-n = 0$

$100000\*100000\*100000\*n^{3}\*n^{4}\*0+nm^{2} = nm^{2}$

Обращаем ваше внимание, что хотя в процессе вычисления значения коэффициента в первом слагаемом последнего многочлена оно и становится больше $10^5$, но в итоге это слагаемое равно $0\cdot n^3\cdot n^4$, значит для него ограничение на величину коэффициента тоже выполняется.