/*
   ACM Western European Region, 1994-95
   Problem B, Bits

   Ed Karrels, October 1996
*/

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


enum TokenType {
   COLON, LCURLY, RCURLY, ARRAY, OF, STRING,
   LPAREN, RPAREN, COMMA, LBRACE, RBRACE, PERIODS, ID, INTEGER, END
};

char *literals[] = {
   ":", "{", "}", "array", "of", "string", "(",
   ")", ",", "[", "]", ".."
};

struct Token {
   int type;
   char id[257];
   int num;
};

enum {
   RECORD_T, ARRAY_T, STRING_T, ENUM_T, RANGE_T
};

struct Type {
   char name[257];
   virtual int Size() = 0;
   Type *next;
};

struct RecordType : public Type {
   Type *element_list;
   int Size();
};

int RecordType::Size() {
   int s=0;
   Type *t;
   t = element_list;
   while (t) {
      s += t->Size();
      t = t->next;
   }
   return s;
}


struct ArrayType : public Type {
   Type *subtype;
   int nel;
   int Size() {
      return nel * subtype->Size();
   }
};

int Nbits(int n) {
   int a=2, b=1;

   while (a<n) {
      a*=2;
      b++;
   }
   return b;
}

struct StringType : public Type {
   int len;
   int Size() {
      return len * 7;
   }
};

struct EnumType : public Type {
   int n_ids;
   int Size() {
      return Nbits(n_ids);
   }
};

struct RangeType : public Type {
   int range;
   int Size() {
      return Nbits(range);
   }
};

Token pushed_token;
int token_is_pushed = 0;

void PushToken(Token tok) {
   pushed_token = tok;
   token_is_pushed = 1;
}

Token NextToken(FILE *inf) {
   Token tok;
   int lit_no;
   char str[300];

   if (token_is_pushed) {
      token_is_pushed = 0;
      return pushed_token;
   }

   do {
      str[0] = getc(inf);
   } while (isspace(str[0]));

   if (isdigit(str[0])) {
      ungetc(str[0], inf);
      fscanf(inf, "%d", &tok.num);
      tok.type = INTEGER;
      return tok;
   }

   if (isalpha(str[0])) {
      int i=0;
      do {
         str[++i] = getc(inf);
      } while (isalpha(str[i]));
      ungetc(str[i], inf);
      str[i] = 0;
      strcpy(tok.id, str);
      if (!strcmp(str, "array")) {
         tok.type = ARRAY;
      } else if (!strcmp(str, "of")) {
         tok.type = OF;
      } else if (!strcmp(str, "string")) {
         tok.type = STRING;
      } else {
         tok.type = ID;
      }
      return tok;
   }

   switch (str[0]) {
      case ':': tok.type = COLON; break;
      case '{': tok.type = LCURLY; break;
      case '}': tok.type = RCURLY; break;
      case '(': tok.type = LPAREN; break;
      case ')': tok.type = RPAREN; break;
      case ',': tok.type = COMMA; break;
      case '[': tok.type = LBRACE; break;
      case ']': tok.type = RBRACE; break;
      case '.': str[1]=getc(inf); tok.type = PERIODS; break;
      default: tok.type = END;
   }

   return tok;
}


int ReadRange(FILE *inf) {
   int s, e;
   Token tok;
   NextToken(inf);   // "["
   tok = NextToken(inf);
   s = tok.num;
   NextToken(inf);   // ".."
   tok = NextToken(inf);
   e = tok.num;
   NextToken(inf);   // "]"
   return e-s+1;
}


Type *ReadType(FILE *inf, int named=0) {
   Token tok;
   RecordType *rtype;
   ArrayType *atype;
   StringType *stype;
   EnumType *etype;
   RangeType *gtype;
   
   Type *type;
   char name[300];

   if (named) {
      tok = NextToken(inf);  // name
      strcpy(name, tok.id);

      tok = NextToken(inf);  // colon
   }

   tok = NextToken(inf);
   switch (tok.type) {
      case LCURLY: // record
         rtype = new RecordType;
         rtype->element_list = 0;
         Type *subtype;

         while (tok = NextToken(inf), tok.type != RCURLY) {
            PushToken(tok);
            subtype = ReadType(inf, 1);
            subtype->next = rtype->element_list;
            rtype->element_list = subtype;
         }
         type = rtype;
         break;

      case ARRAY: // array
         atype = new ArrayType;
         atype->nel = ReadRange(inf);
         NextToken(inf);  // "of"
         atype->subtype = ReadType(inf);
         type = atype;
         break;

      case STRING: // string
         stype = new StringType;
         NextToken(inf);  // "("
         tok = NextToken(inf);  // string length
         stype->len = tok.num;
         NextToken(inf);  // ")"
         type = stype;
         break;

      case LPAREN: // enum
         etype = new EnumType;
         etype->n_ids = 0;
         while (tok.type != RPAREN) {
            tok = NextToken(inf);   // identifier
            tok = NextToken(inf);   // comma or rparen
            etype->n_ids++;
         }
         type = etype;
         break;

      case LBRACE: // range
         gtype = new RangeType;
         PushToken(tok);
         gtype->range = ReadRange(inf);
         type = gtype;
         break;

      default:
         printf("syntax error.\n");
         exit(0);
   }

   if (named) {
      strcpy(type->name, name);
   }

   return type;
}


int main(int argc, char **argv) {
   FILE *inf;
   Token tok;
   int ntypes, type_no;
   Type *type;

   inf = stdin;

   fscanf(inf, "%d", &ntypes);
   for (type_no=0; type_no<ntypes; type_no++) {

      type = ReadType(inf, 1);
      printf("A \"%s\" message requires %d bits.\n", type->name, type->Size());
   }
   return 0;
}