Problem B

Bits

It is not always easy to transfer data from one computer system to the other. You need proper standards for data encoding, and may also need to compress data to save bandwidth and thus reduce costs.

To assist the designer in making implementation choices related to the available bandwidth, a tool is required that computes the size of each message in bits. The tool has to read and interpret the format of each message to do so.

A message can best be described by giving the underlying grammar, which uses the following terminals:

id
a sequence of letters of length L (1<=L<=256)
integer
a number between -10000 and 10000 (inclusive)
"word"
the literal string of characters word

A message is defined by the following grammar:

message  ::= data
data     ::= id ":" type
type     ::= record | array | string | enum | range
record   ::= "{" data+ "}"
array    ::= "array" range "of" type
string   ::= "string" "(" integer ")"
enum     ::= "(" id-list ")"
id-list  ::= id | (id "," id-list)
range    ::= "[" integer ".." integer "]"

Note that the message grammar is specified according to the following notational conventions:

x y      sequence: x followed by y
x | y    choice: x or y
x+       repetition: one or more occurrences of x
( )      used for grouping

Any two tokens may be separated by an arbitrary amount of white space (blanks, tabs an newlines). White space does not occur within tokens.

The (minimal) amount of bits needed to transmit a message can be computed using the following rules:

record : sum of the sizes of the fields
array : size of the component type, multiplied by the number of elements in the range
string : the length, multiplied by 7 bits
enum : smallest number of bits in which all id's can be distinguished
range : smallest number of bits in which all range values can be distinguished

Input

The input contains on the first line the number of test cases (N). Each test case will contain message according to the grammar above. Messages may be separated by an arbitrary amount of white space. You may assume that the input is syntactically correct. For each range 'L..H', it holds that L<=H. A string consists of a positive number of characters.

Output

For each message, output the sentence: '

A "id" message
requires S bits.

', where id is the identifier of the message and S its size in bits.

Sample Solution

Sample Input

3
year : [1970..2030]
team : {
        name : string(14)
        members : array [1..3] of {
                sex : ( male, female )
                name : string(20)
                age : [16..30]
        }
        position : [1..40]
}
jurynames : array [1..3] of string(20)

Sample Output

A "year" message requires 6 bits.
A "team" message requires 539 bits.
A "jurynames" message requires 420 bits.

This page maintained by Ed Karrels.
Last updated September 20, 1999

1994-1995 ACM International Collegiate Programming Contest Western European Regional