Even a Kindergartner Could Solve This

Doyoung thinks he is extremely smart. To knock him down a peg, Dongjin prepared a single problem.

• Dongjin asked, "Can you explain the grammar of a set to me?"
• Doyoung answered, "Of course! A set is a list enclosed by two curly braces { }. The list may be empty, or its elements may be other sets or a single character from a given alphabet."
• "Then if I give you a string, can you tell whether it is a grammatically valid set?"
• "Of course, even a kindergartner could solve a problem like this."

Dongjin defined the grammar of a set as follows. (This is not the real definition of a set; he made it up only to tease Doyoung.)

Set ::= "{" Elementlist "}"
Elementlist ::= <empty> | List
List ::= Element | Element "," List
Element ::= Atom | Set
Atom ::= "{" | "}" | ","

Here \<empty> means that the list may be empty.

The catch is that the alphabet (the single characters allowed as elements) consists of exactly the symbols {, }, and ,, which also play a crucial role in the grammar. Because of this overlap, deciding whether a string is a set is trickier than it looks. Write an efficient program that decides whether a given string is a valid set according to the grammar above.

The first line contains the number of strings $N$ to check.

Each of the next $N$ lines contains one string to be checked for being a grammatically valid set. Each string has length between $1$ and $200$ and consists only of the three characters {, }, and ,.

Print one line for each string. For the $i$-th string ($i$ starts from $1$), print Word #i: Set if it is a grammatically valid set, and Word #i: No Set otherwise.