prob10.cpp

/*
	Mercer 2018 Problem 10: Nth Derivative.

	Charles Bailey. 03/01/2018
*/
#include <bits/stdc++.h>
#include <regex>

typedef long long ll;

struct term {
	bool neg;
	ll coeff;
	ll power;

	std::string to_string(const bool& first) {
		std::stringstream ret;
		if (coeff == 0) return "";
		if (neg)
			ret << "-";
		else if (!first)
			ret << "+";

		if (coeff > 1 || power == 0)
			ret << coeff;
		if (power != 0 && coeff > 1)
			ret << "*x";
		else if (power != 0)
			ret << "x";
		if (power > 1 || power < 0)
			ret << "^" << power;
		return ret.str();
	}
};

static void one_case(void) {
	const std::regex PATTERN{"(\\+|-)?(\\d*)\\*?(x?((?:\\^)-?\\d+)?)"};

	ll n;
	std::scanf("%lld",&n);

	std::string str;
	std::cin >> str;

	std::smatch sm;
	bool first = true;
	while (std::regex_search(str, sm, PATTERN) && !sm[0].str().empty()) {

		term tmp = {sm[1] == "-", sm[2].str().empty() ? 1 : std::stoi(sm[2].str()),
		            sm[4].str().empty() && sm[3].str().empty() ? 0 : (sm[4].str().empty() ? 1 : std::stoi(sm[4].str().substr(1)))};

		for (ll i = 1; i <= n; ++i) {
			tmp.coeff *= tmp.power--;
			if (tmp.coeff < 0)
				tmp.neg = !tmp.neg;
			tmp.coeff = std::abs(tmp.coeff);
		}

		std::printf("%s", tmp.to_string(first).data());
		first = false;
		str = sm.suffix();
	}
	std::putchar('\n');
}

int main(void) {
	ll t;
	std::scanf("%lld", &t);
	while(t--) one_case();
	return 0;
}