모호한 암호

Susie와 Calvin은 같은 반 친구다. Calvin은 수업 시간에 쪽지를 Susie에게 몰래 전달하려고 한다. 쪽지가 다른 사람 손에 들어가도 선생님이나 다른 친구들이 내용을 알 수 없게 하려는 것이다. 그래서 Calvin은 메시지를 암호화하는 체계를 고안했다.

Calvin은 매번 Susie에게 단어 하나만 전달하며, 그 단어는 대문자로만 이루어져 있다. Susie와 이야기하고 싶어 신이 난 Calvin은 단어를 다음과 같이 암호화한다.

• Calvin은 알파벳에서의 위치에 따라 각 글자에 수를 부여한다. A = 0, B = 1, ..., Z = 25.
• 단어의 각 글자에 대해, Calvin은 그 글자에 인접한 1개 또는 2개의 글자의 값을 더한다. 그 합을 26으로 나눈 나머지를 구하고, 이것이 그 글자의 새 값이 된다. Calvin은 이 값을 앞에서처럼 알파벳 위치에 따라 다시 대문자로 바꾼다.
• 암호화된 단어는 이 방법으로 단어의 모든 글자를 암호화해 얻는다. 각 글자의 암호화는 원래 암호화되지 않은 메시지의 글자만을 바탕으로 하며, 이미 암호화된 글자는 사용하지 않는다.

Calvin이 Susie에게 쓰는 쪽지 하나를 보자. Calvin은 항상 배가 고프기 때문에 Susie에게 또 먹고 싶다고 알리고 싶어 한다. Calvin은 SOUP이라는 단어를 다음과 같이 암호화한다.

• S = 18, O = 14, U = 20, P = 15.

• Calvin은 각 글자를 이웃 글자의 값에 따라 암호화한다.

  • 첫 번째 글자: 14 mod 26 = 14.
  • 두 번째 글자: (18 + 20) mod 26 = 12.
  • 세 번째 글자: (14 + 15) mod 26 = 3.
  • 네 번째 글자: 20 mod 26 = 20.

• 값 14 12 3 20은 글자 OMDU에 해당하며, 이것이 Calvin이 Susie에게 쪽지에 적어 줄 암호화된 단어다.

Calvin은 전혀 복호화할 수 없는 단어는 Susie에게 보내지 않는다. 예를 들어 Calvin은 APE라는 단어를 보내지 않는다. APE는 유효한 복호화가 하나도 없기 때문이다. 즉, Calvin이 암호화해서 APE가 되는 단어는 존재하지 않는다.

하지만 Calvin의 체계는 완벽하지 않아서, 그가 보내는 단어 중에는 여러 단어로 복호화될 수 있는 것도 있다. 예를 들어 BCB는 ABC나 CBA 등 여러 가지로 복호화될 수 있다.

Susie는 어제도 학교 과제를 하느라 밤을 새웠고, 너무 피곤해서 Calvin의 메시지를 복호화할 힘이 없다. 그녀는 여러분의 도움이 필요하다!

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 대문자로 이루어진 문자열 W 한 줄이다. W는 Calvin이 보낸 암호화된 단어다.

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, y는 복호화된 단어다. 복호화된 단어를 유일하게 결정할 수 없다면 AMBIGUOUS를 출력한다.

• 1 ≤ T ≤ 100.
• W는 대문자 영어 알파벳으로만 이루어져 있다.
• W는 하나 이상의 단어로 복호화할 수 있다. 즉, W는 어떤 단어를 암호화한 결과다.
• W는 AMBIGUOUS라는 단어로 복호화되지 않는다. 이 값은 복호화가 모호할 때만 출력한다.

마지막 예제는 Small 데이터셋에는 나오지 않는다.

예제 #1과 #2는 문제 지문에서 설명했다.

예제 #3에서 AOAAAN으로 암호화되는 단어는 BANANA뿐이다.