In this problem, you will be given a polynomial, you have to print what it becomes after differentiation.

Following are the rules for differentiation:
- For a polynomial f(x), its differentiation is defined as f'(x).
- If a is a constant, then differentiation of af(x) is af'(x).
- If f(x) = h(x) + g(x) , then f'(x) = h'(x) + g'(x) 
- If f(x) = x n, then f'(x) = nxn-1. This is true for all  n ≠ 0 .
- If f(x) = c, where c is a constant, f'(x) = 0.

If you are still uncomfortable with differentiation, please read the following:
-  Link to Wikihow page
- Link to Wikipedia entry.

-----Input-----

First line contains T, the number of test cases to follow. 

Each test case contains the follows, the first line contains N, the number of non zero terms in the polynomial. Then N lines follow, each line contains a pair of integer which denotes a term in the polynomial, where the first element denotes the coefficient (a) and the second denotes the exponent (p) of the term.

-----Output-----
Print the polynomial after differentiation in the desired format as described below.
-  If the coefficient of a term in the output polynomial is 3, and the corresponding exponent is 2, print it as 3x^2
- Print " + " (with single space on both side) between each output term.
-  Print the terms in decreasing value of exponent.
-  For the constant term (if any), you have to just print the coefficient. You should not print x^0.

-----Constraints-----
- 1 ≤ T ≤ 10
-   Subtask 1 (20 points)

- 1 ≤ N ≤ 3
- 1 ≤ a ≤ 10
- 0 ≤ p ≤ 10
- Subtask 2 (80 points)

- 1 ≤ N ≤ 10000
- 1 ≤ a ≤ 100000000
- 0 ≤ p ≤ 100000000
-  No two inputs in a test case will have the same exponent.

-----Example-----
Input:
2
1
1 2
3
1 3
1 1
1 0

Output:
2x^1
3x^2 + 1

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
def ans(l):
	s = ''
	i = 0
	while i < len(l):
		temp = l[i]
		k = temp[1]
		if k != 0:
			s += str(temp[0]) + 'x^' + str(k)
		else:
			s += str(temp[0])
		i += 1
		if i < len(l):
			s += ' + '
	if len(s) > 0:
		return s
	else:
		return '0'
test = int(input())
while test != 0:
	test -= 1
	N = int(input())
	l = []
	while N != 0:
		(n, m) = list(map(int, input().split()))
		if m > 0:
			l += [[n * m, m - 1]]
		N -= 1
	print(ans(l))


T = int(input())
for i in range(T):
	N = int(input())
	poly = [(0, 0) for j in range(N)]
	diff = [(0, 0) for j in range(N)]
	for j in range(N):
		poly[j] = list(map(int, input().split()))
		diff[j] = [poly[j][1] - 1, poly[j][0] * poly[j][1]]
	diff.sort()
	diff.reverse()
	for j in range(N):
		if j == 0:
			if diff[j][0] == -1:
				print(0, end=' ')
			elif diff[j][0] == 0:
				print('%d' % diff[j][1], end=' ')
			else:
				print('%dx^%d' % (diff[j][1], diff[j][0]), end=' ')
		elif diff[j][0] == -1:
			break
		elif diff[j][0] == 0:
			print('+ %d' % diff[j][1], end=' ')
		else:
			print('+ %dx^%d' % (diff[j][1], diff[j][0]), end=' ')
	print('')


t = int(input())
st = ''
x = 0
zt = ''
while t:
	t -= 1
	n = int(input()) - 1
	a = [int(x) for x in input().split()]
	if a[0] == 0 or a[1] == 0:
		x = 0
	elif a[1] > 1:
		st += str(a[1] * a[0]) + 'x^' + str(a[1] - 1)
	elif a[1] == 1:
		st += str(a[0])
	while n:
		n -= 1
		a = [int(x) for x in input().split()]
		if a[0] == 0 or a[1] == 0:
			x = 0
		elif a[1] > 1:
			st += ' + ' + str(a[1] * a[0]) + 'x^' + str(a[1] - 1)
		elif a[1] == 1:
			st += ' + ' + str(a[0])
	for i in range(len(st)):
		if st[i] == ' ' or st[i] == '+':
			continue
		else:
			break
	st = st[i:]
	print(st)
	st = ''


t = int(input())
st = ''
x = 0
while t:
	t -= 1
	n = int(input()) - 1
	a = [int(x) for x in input().split()]
	if a[0] == 0 or a[1] == 0:
		x = 0
	elif a[1] > 1:
		st += str(a[1] * a[0]) + 'x^' + str(a[1] - 1)
	elif a[1] == 1:
		st += str(a[0])
	while n:
		n -= 1
		a = [int(x) for x in input().split()]
		if a[0] == 0 or a[1] == 0:
			x = 0
		elif a[1] > 1:
			st += ' + ' + str(a[1] * a[0]) + 'x^' + str(a[1] - 1)
		elif a[1] == 1:
			st += ' + ' + str(a[0])
	print(st)
	st = ''


from sys import stdin
T = int(stdin.readline().strip())
for x in range(T):
	N = int(stdin.readline().strip())
	ansList = []
	for i in range(N):
		(a, p) = list(map(int, stdin.readline().strip().split()))
		if p > 1:
			ansList.append('%dx^%d' % (a * p, p - 1))
		elif p == 1:
			ansList.append('%d' % (a * p))
	value = True
	ans = 0
	for k in range(ansList.__len__()):
		if not 'x' in ansList[k]:
			ans += int(ansList[k])
			continue
		else:
			value = False
	if value:
		print(ans)
		continue
	for j in range(ansList.__len__()):
		if j != ansList.__len__() - 1:
			print(ansList[j], '+', end=' ')
		else:
			print(ansList[j])


from sys import stdin
T = int(stdin.readline().strip())
for x in range(T):
	N = int(stdin.readline().strip())
	ansList = []
	for i in range(N):
		(a, p) = list(map(int, stdin.readline().strip().split()))
		if p > 1:
			ansList.append('%dx^%d' % (a * p, p - 1))
		elif p == 1 and a != 0:
			ansList.append('%d' % (a * p))
	for j in range(ansList.__len__()):
		if j != ansList.__len__() - 1:
			print(ansList[j], '+', end=' ')
		else:
			print(ansList[j])


def f(x):
	return x[1]
for t in range(int(input())):
	n = int(input())
	s = ''
	l = []
	for i in range(n):
		(a, p) = list(map(int, input().split()))
		l.append((a, p))
	l = sorted(l, key=f, reverse=True)
	for i in range(n):
		(a, p) = l[i]
		a = a * p
		p -= 1
		if a == 0:
			continue
		if p == 0:
			s += ' + ' + str(a)
		else:
			s += ' + ' + str(a) + 'x^' + str(p)
	s = s[3:]
	if len(s) == 0:
		print(0)
	else:
		print(s)


import sys
for __ in range(eval(input())):
	n = eval(input())
	(ans, const) = ('', False)
	for i in range(n):
		(p, a) = list(map(int, sys.stdin.readline().split()))
		(coeff, power) = (0, 0)
		if a > 0:
			coeff = a * p
			power = a - 1
			if power != 0:
				if n == 1:
					ans += str(coeff) + 'x^' + str(power)
					const = True
				else:
					ans += str(coeff) + 'x^' + str(power) + ' + '
			else:
				ans += str(coeff)
				const = True
	print(0 if ans == '' else ans.strip() if const else ans[:len(ans) - 3].strip())


CA = []
IA = []
for i__i in range(eval(input())):
	n = eval(input())
	for __ in range(n):
		(zz, ex) = list(map(int, input().split()))
		if ex == 0:
			continue
		if ex > 1:
			CA.append(str(zz * ex) + 'x^' + str(ex - 1))
		if ex == 1:
			IA.append(zz * ex)
	k = sum(IA)
	if k > 0:
		CA.append(str(k))
	str1 = ' + '.join((str(e) for e in CA))
	if len(str1) >= 1:
		print(str1)
	else:
		print('0')
	CA[:] = []
	IA[:] = []


CA = []
IA = []
for II_II in range(eval(input())):
	n = eval(input())
	for KK_KK in range(n):
		(cof, exp) = list(map(int, input().split()))
		if exp == 0:
			continue
		if exp > 1:
			CA.append(str(cof * exp) + 'x^' + str(exp - 1))
		if exp == 1:
			IA.append(cof * exp)
	k = sum(IA)
	if k > 0:
		CA.append(str(k))
	str1 = ' + '.join((str(e) for e in CA))
	if len(str1) >= 1:
		print(str1)
	else:
		print('0')
	CA[:] = []
	IA[:] = []


CharacterArray = []
IntegerArray = []
for II_II in range(eval(input())):
	n = eval(input())
	for KK_KK in range(n):
		(cof, exp) = list(map(int, input().split()))
		if exp == 0:
			continue
		if exp > 1:
			CharacterArray.append(str(cof * exp) + 'x^' + str(exp - 1))
		if exp == 1:
			IntegerArray.append(cof * exp)
	k = sum(IntegerArray)
	if k > 0:
		CharacterArray.append(str(k))
	str1 = ' + '.join((str(e) for e in CharacterArray))
	print(str1)
	CharacterArray[:] = []
	IntegerArray[:] = []


arr = []
for II_II in range(eval(input())):
	n = eval(input())
	for KK_KK in range(n):
		(cof, exp) = list(map(int, input().split()))
		if exp == 0:
			continue
		if exp > 1:
			arr.append(str(cof * exp) + 'x^' + str(exp - 1))
		if exp == 1:
			arr.append(str(cof * exp))
	str1 = ' + '.join((str(e) for e in arr))
	print(str1)
	arr[:] = []


import operator

def getTerm(v, first=False):
	a = v[0]
	p = v[1]
	s = ''
	if a != 0:
		if not first:
			s += ' + '
		if p == 0:
			s += str(a)
		else:
			s += str(a) + 'x^' + str(p)
	return s

def main():
	i = 0
	t = int(input())
	while i < t:
		n = int(input())
		v = []
		ans = ''
		for x in range(0, n):
			m = input().split(' ')
			tup = (int(m[0]) * int(m[1]), int(m[1]) - 1)
			v.append(tup)
		v = sorted(v, key=lambda x: (-x[1], x[0]))
		fterm = v[0]
		if fterm[1] != 0 and fterm[0] != 0:
			ans = str(fterm[0]) + 'x^' + str(fterm[1])
		else:
			ans = str(fterm[0])
		for j in range(1, n):
			ans += getTerm(v[j])
		print(ans)
		i += 1

def __starting_point():
	main()
__starting_point()


t = int(input())
while t:
	n = int(input())
	ans = ''
	c = []
	zero = 0
	while n:
		(a, b) = input().split()
		a = int(a)
		b = int(b)
		if b == 0:
			zero += 1
		if b == 1:
			c.append(repr(a))
		elif b != 0:
			c.append(repr(a * b) + 'x^' + repr(b - 1))
		n -= 1
	l = len(c)
	if l == 0:
		print(0)
	else:
		cnt = 0
		for i in c:
			print(i, end=' ')
			cnt += 1
			if cnt != l:
				print(' + ', end=' ')
		print('\n', end=' ')
	t -= 1


t = eval(input())
while t != 0:
	n = eval(input())
	x = []
	y = []
	for i in range(0, n):
		b = list(map(int, input().split(' ')))
		x.append(b[1])
		y.append(b[0])
	xy = list(zip(*sorted(zip(x, y))))
	x = xy[0]
	y = xy[1]
	for i in reversed(list(range(0, n))):
		if x[i] != 0:
			if i != n - 1:
				print('+', end=' ')
			if x[i] == 1:
				print('%d' % (x[i] * y[i]), end=' ')
			else:
				print('%dx^%d' % (x[i] * y[i], x[i] - 1), end=' ')
	print()
	t = t - 1


def myKey(l):
	return -l[1]
t = int(input())
for tests in range(t):
	n = int(input())
	ca = []
	for i in range(n):
		l = input()
		l = l.split()
		l[0] = int(l[0])
		l[1] = int(l[1])
		ca.append(l)
	if n == 1 and ca[0][1] == 0:
		print('0')
		continue
	ca.sort(key=myKey)
	for i in range(n):
		ca[i][0] *= ca[i][1]
		ca[i][1] -= 1
	ans = ''
	for i in range(n - 1):
		if ca[i][0] != 0:
			if ca[i][1] != 0:
				ans += str(ca[i][0]) + 'x^' + str(ca[i][1]) + ' + '
			else:
				ans += str(ca[i][0]) + ' + '
	if ca[n - 1][0] != 0:
		if ca[n - 1][1] != 0:
			ans += str(ca[n - 1][0]) + 'x^' + str(ca[n - 1][1])
		else:
			ans += str(ca[n - 1][0])
	else:
		ans = ans[:-3]
	print(ans)