#include <stdio.h>
#include <string.h>

char c[100000];__int64 a[100001],b[100001],m[100001];__int64 i,g,l,n,p,r,v,s,t,flag;

void Finddigit(__int64 k)
{
	  v=-1;
	  for(r=k-1;r>=0;r--){
		  if(c[r]=='+'){v=r;break;}else if(c[r]=='-'){v=r;a[i]=-a[i];break;}
	  }
	  if(v!=k-1){s=0;for(r=v+1;r<k;r++){s*=10;s+=c[r]-0x30;}a[i]*=s;}
}
void Findm(__int64 k)
{
	if(c[k+1]=='^'){
		s=0;
		flag=0;
		for(r=k+2;c[r];r++){if(c[r]>='0' && c[r]<='9'){s*=10;s+=c[r]-0x30;flag=1;}else{break;}}
		if(flag==1){b[i]=s;}
	}
}

void chang()
{
    for(i=1;i<=l;i++){a[i]*=b[i];--b[i];}
}
void p1()
{
	flag=0;
    for(i=1;i<=l;i++){
		if(b[i]<0){continue;}
		flag=1;
		  if(b[i]==0){printf("%I64d",a[i]);}
		  else if(a[i]!=1 && a[i]!=-1){printf("%I64d",a[i]);}
		  else if(a[i]==-1){printf("-");}
		  if(b[i]!=0){printf("x");}
		  if(b[i]>1){printf("^%I64d",b[i]);}
	}
	if(flag==0){printf("0");}
	printf("\n");
}
void p2()
{
	flag=0;
    for(i=1;i<=l;i++){
		if(b[i]<0){continue;}
		flag=1;
		  if(b[i]==0){printf("%I64d",a[i]);}
		  else if(a[i]!=1 && a[i]!=-1){printf("%I64d",a[i]);}
		  else if(a[i]==-1){printf("-");}
		  if(b[i]!=0){printf("(%I64d)",g);}
		  if(b[i]>1){printf("^%I64d",b[i]);}
	}
	if(flag==0){printf("0");}
	printf("\n");
}
void p3()
{
	p=0;
	flag=0;
    for(i=1;i<=l;i++){
		  if(b[i]<0){continue;}
		  flag=1;
		  s=a[i];for(r=1;r<=b[i];r++){s*=g;}{if(i>1 && s>=0)printf("+");printf("%I64d",s);}
		  p+=s;
	}
	if(flag==0){printf("0");}
    printf("\n");
}
void p4()
{
	printf("%I64d\n",p);
}
int main()
{
	  scanf("%I64d",&n);
	  for(t=1;t<=n;t++){
	  scanf("%I64d",&g);
	  memset(c,0,sizeof(c));
	  scanf("%s",&c);
	  printf("POLYNOMIAL %d\n",t);
	  l=0;for(i=0;c[i];i++){if(c[i]=='x'){m[++l]=i;}}
	  for(i=1;i<=l;i++){a[i]=1;b[i]=1;}
	  for(i=1;i<=l;i++){Finddigit(m[i]);Findm(m[i]);}
	  printf("%s\n",c);
	  chang();
	  p1();
	  p2();
	  p3();
	  p4();
	  }
      return 0;
}