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

Difficulty: interview

Starter code:

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))


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 += " + "
 return s

 
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))


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 += " + "
 return s


 
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))


# cook your code here
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=' ')
  else:
   if 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))
 #print IntegerArray
 k=sum(IntegerArray)
 if k>0: CharacterArray.append(str(k))
 #print CharacterArray
 str1 = ' + '.join(str(e) for e in CharacterArray)
 if len(str1)>=1: print(str1)
 else : print("0")
 CharacterArray[:]=[]
 IntegerArray[:]=[]
 
 


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))
 #print IntegerArray
 k=sum(IntegerArray)
 if k>0: CharacterArray.append(str(k))
 #print CharacterArray
 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))
 #print arr
 str1 = ' + '.join(str(e) for e in arr)
 print(str1)
 #"+".join(l)
 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)

  # sort descending
  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()

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)

  # sort descending
  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 = fterm[0]
 
  for j in range(1, n):
   ans += getTerm(v[j])
 
  print(ans)
 
  i+=1
 
def __starting_point():
 main()
__starting_point()

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]))
  ans = getTerm(v[0], True)
 
  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


# cook your code here
t=eval(input())
while(t!=0):
 n=eval(input())
 x=[]
 y=[]
 #print a
 for i in range(0,n):
  b=list(map(int,input().split(' ')))
  #print b
  
  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()
 
 # print x
#print y
 t=t-1

# your code goes here
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)

# your code goes here
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)
 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)