시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 7 2 2 50.000%

문제

도영이는 자신이 굉장히 똑똑하다고 생각한다. 동진이는 도영이의 기를 죽이기 위해 한 가지 문제를 준비해 왔다.

  • 동진이가 도영이에게 물었다. "내게 집합의 문법을 설명해 줄 수 있어?"
  • 도영이가 동진이에게 말했다. "당연하지! 두 개의 꺾쇠 괄호로 둘러싸여 있는 리스트를 포함하는 것이라구. 리스트는 비어 있을 수도 있고, 원소로 다른 집합이나 주어진 alphabet 한 글자를 가질 수 있어."
  • "그럼 내가 어떤 문자열을 주면 문법적으로 집합이 맞는지 알려 줄 수 있어?"
  • "당연하지! 이런 문제는 유치원생도 해결할 수 있어."

좋았어! 동진이의 계획대로 되고 있다. 동진이는 집합의 문법을 다음과 같이 정의했다. (물론 이게 실제 집합의 문법은 아니다. 동진이가 도영이를 곯려주기 위해 만들었을 뿐, 절대 이것을 이산 구조 수업 시간에 거론하며 교수님과 싸우지는 말도록 하자.)

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

<empty>는 리스트가 비어 있을 수도 있음을 의미한다.

도영이는 이 문제가 생각보다 어렵다는 것을 깨닫게 되었다. 공교롭게도 집합의 원소일 수 있는 alphapet이 문법적으로 중요한 역할을 하는 기호들이었던 것이다. 결국 도영이는 "{", "}", ","를 alphabet으로 사용하는 문자열이 집합인지를 효율적으로 판정하는 일은 어렵다고 주장했다.

동진이는 이러한 도영이의 주장에 반박하기 위해, 이 일을 해 주는 효율적인 프로그램을 짜기로 했다. 동진이를 도와서 프로그램을 짜는 것을 도와주시오.

입력

입력의 첫 번째 줄에 판별할 문자열의 수가 주어진다.

다음 줄부터는 문법적으로 집합인지 아닌지를 판별해야 하는 문자열이 주어진다. 각 문자열의 길이는 1 이상 200 이하이며, "{", "}", ","로만 이루어져 있다.

출력

각 줄마다 해당 문자열이 문법적으로 집합이 맞는지 아닌지를 출력하시오. 출력 형식은 아래의 예제 출력을 참고하시오.

예제 입력

4
{}
{{}}
{{}},{,}}
{,,}

예제 출력

Word #1: Set
Word #2: Set
Word #3: Set
Word #4: No Set

힌트