#include <fstream.h>
#include <iostream.h>

#include <stdio.h>
#include <string.h>
// #include <stdlib.h>
// #include <math.h>
// #include <ctype.h>

#define oo 1000000000
#define PI 3.14159265389793
#define EPS 1e-9

#define DBG(x) 
#define PRINT(x) cout << (#x) << " = " << x << endl
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))

int polynom[1000];
int constloop[1000];

char keyword[1000];
int ebene;
int cebene;

ifstream in("complex.in");

void test(char *a, char *b) {
  if( strcmp(a,b) != 0) cerr << "ERROR in TEST" << a << " b " << b << endl;
}

int eq(char *a, char *b) { return (strcmp(a,b) == 0); }

int op() {
  int number;
  in >> number;
  //polynom[ebene]+=number;
  in >> keyword;
  DBG( cout << "OP" << number << endl );
  return number;
}

int statementlist(); // forward for loop

int loopstatement () {
  char c;
  int mal=1;
  int ret=0;

  in >> c;
  if( c == 'n' ) {
    ebene++;
    cebene++;
    in >> keyword;
    for(int i=0; i<cebene-1;i++) mal*=constloop[i];
    DBG( cout << "Malvorconst : " << mal << endl );
    polynom[ebene]+=mal*statementlist();
    cebene--;
    ebene--;
  } else {
    in.putback(c);
    int number;

    in >> number;
    in >> keyword;
    DBG( cout << "Constloop before : " << constloop[ebene] << endl);
    constloop[cebene]*=number;
    DBG( cout << "Setting constloop " << constloop[cebene] << " ebene " << ebene << " number " << number << endl);
    //    for(int i=0; i<cebene;i++) mal*=constloop[i];
    //polynom[ebene]
    cebene++;
    ret = number*statementlist();
    cebene--;
    constloop[cebene]/=number;
    DBG( cout << "Number should be 1 " << constloop[cebene] << endl );
  }
  in >> keyword;
  DBG( cout << "Loop "<<cebene << "returned" << ret << endl );
  return ret;
}

int statementlist() {
  int sum=0;

  while( !eq(keyword, "END") ) {
    if( eq(keyword, "LOOP" ) ) {
    DBG( cout << "  Sum Before " << sum );
      sum+=loopstatement(); // reads next itself
      //      return 0;
    DBG( cout << "  Sum After " << sum << endl );
    } else if( eq(keyword, "OP") )
      sum+=op(); // reads next itself
  }
  DBG( cout << "Statementlist retured " << sum << endl );
  return sum;
}

int program() {
  int ret;

  //  in >> keyword;
  DBG( test(keyword, "BEGIN") );
  in >> keyword;
  ret = statementlist();
  DBG( test(keyword, "END") );
  in >> keyword;
  //  DBG( cout<< "Read keyword after end: " << keyword << endl );
  return ret;
}

void output() {
  bool didSth=false;
  
  cout << "Runtime = ";
  for(int i=999; i>=0; i--) {
    if( polynom[i] > 0) {
      if( didSth ) cout << "+";
      didSth=true;
      if( polynom[i] != 1 || (i==0) ) {
	cout << polynom[i];
      }
      if( polynom[i] != 1 && i>=1)
	cout << "*";
      if( i>1 ) cout << "n^" << i;
      else if(i==1) cout << "n";
    }
  }
  if( !didSth ) cout << "0";
  cout << "\n\n";
}

int main(){
  int numberOfProblems;
 
  
  in >> numberOfProblems;
  in >> keyword;
  for(int i=0; i<numberOfProblems; i++) {
    cout << "Program #" << (i+1) << endl;
    for(int j=0; j<1000; j++) { polynom[j]=0; constloop[j]=1; }
    ebene=0;
    polynom[0]+=program();
    output();
  }

  in.close();
  return 0;
}