Sizeof

Most high-level programming languages support structured data types. Pascal has record types, C has struct types, and C++ and Java have class types. A structured type is built from component types, and a value of a structured type stores a value for each of its components.

When we store structured data we must account for memory alignment. In a classic Von Neumann machine, memory is addressed in units of words, so for fast access every datum is aligned to a word boundary. A word is a fixed whole number of bytes, the same for a given machine. A machine whose word is W bytes is called a W-byte computer.

Alignment causes memory fragmentation. For example, a 1-byte datum occupies 4 bytes on a 4-byte computer. In general, a datum of type T wastes space whenever the size of T is not a multiple of the word size. Consider this C structure.

struct A {
    char a;
    struct {
        int x;
        char c;
    } b;
};

Assume sizeof(char) = 1 and sizeof(int) = 4, and suppose we store a value of type A on a 2-byte computer. Field a needs only 1 byte in principle, but 2 bytes in practice because of alignment. Field b.x fills exactly two words, so it needs 4 bytes. Field b.c needs one full word even though sizeof(b.c) is 1, so it needs 2 bytes. Altogether a value of type A needs 8 bytes on a 2-byte computer. On a 4-byte computer it needs 12 bytes, and on a 1-byte computer only 6 bytes.

Write a program that reads the word size W of a computer and a structured type declaration T, and computes how many bytes are needed to store a value of type T on a W-byte computer, taking memory alignment into account.

For simplicity, the language contains only structure types and primitive types: no pointers, no references, and no arrays. A structure is introduced by the keyword struct, immediately followed by the structure's identifier. A primitive type is written Tn, where n is a single positive decimal digit (1 through 9) giving the number of bytes needed to store one value of type Tn. Because n must be a single digit from 1 to 9, names such as T0 or T101T are ordinary identifiers, not primitive types. The structure name serves as a type name, and it may be omitted when the structure type is not referred to elsewhere. Apart from these points, all other rules and the meaning of the declarations follow the C language. For instance, an empty structure such as struct Empty {}; may be declared, and its size is 0, as in C. Rewritten with these rules, the declaration above becomes.

struct A {
   T1 a;
   struct {
       T4 x;
       T1 c;
   } b;
};

Even when every syntactic rule is obeyed, a declaration can still be illegal. There are two kinds of semantic errors to detect: (1) declaring a duplicate type or a duplicate field within the same scope, and (2) declaring a recursive structure. Your program must detect both.

Input is read from standard input. The first line contains the number of test cases N. Each test case begins with a line holding the word size W (0 < W < 100), the number of bytes in one word. The following lines hold one structure type declaration. Each test case ends with a line that begins with a single dollar sign $. Every input line is shorter than 1,000 characters. Every test case is free of syntactic errors, though it may contain semantic errors.

Write to standard output. For each test case, write on its own line the size of the structure in bytes, accounting for memory alignment on a machine whose word size is the W given for that test case. If the declaration is itself illegal, write error instead.