모호한 암호

Susie와 Calvin은 같은 반 친구이다. Calvin은 쪽지가 엉뚱한 사람의 손에 들어갈 경우를 대비해, 선생님이나 다른 반 친구들이 무슨 이야기를 하는지 알지 못하도록 수업 중에 Susie에게 쪽지를 전달하고 싶어 한다. Calvin은 자신의 메시지를 암호화하는 체계를 고안했다.

Calvin은 Susie에게 매번 단어 하나만 전달하며, Susie와 이야기할 생각에 매우 들뜬 Calvin이 보내는 그 단어는 대문자로만 이루어진다. 각 단어는 다음과 같이 암호화한다:

• Calvin은 알파벳에서 각 문자의 위치를 기준으로 각 문자에 수를 할당한다. 여기서 A = 0, B = 1, ..., Z = 25이다.

• 단어의 모든 문자에 대해, Calvin은 그 문자와 단어에서 인접한 1 또는 2 문자의 값을 더하여 해당 문자의 암호화된 값을 구한다. 그 합을 26로 나눈 나머지를 취하며, 이것이 해당 문자의 새로운 값이다. 그런 다음 Calvin은 이전과 마찬가지로 알파벳에서의 위치에 따라 그 값을 다시 대문자로 변환한다.

• 이 방법으로 단어의 모든 문자를 암호화하여 암호화된 단어를 결정한다. 각 문자의 암호화는 이미 암호화된 문자가 아니라 암호화되지 않은 원본 메시지의 문자만을 기반으로 한다

Calvin이 Susie에게 쓰고 있는 쪽지 중 하나를 살펴보자. Since 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을 Susie에게 보내지 않는다. (즉, Calvin이 암호화하여 APE이 될 수 있는 단어는 없다.)

하지만 Calvin의 체계는 완벽하지 않으며, 그가 Susie에게 보내는 단어 중 일부는 실제로 여러 단어로 복호화될 수 있어 모호함이 생긴다! 예를 들어, BCB은 여러 가능성 가운데 ABC 또는 CBA로 복호화될 수 있다.

Susie는 학교 과제를 끝내기 위해 어제도 밤을 꼬박 새웠고, Calvin의 메시지를 복호화하기에는 너무 피곤하다. Susie에게는 여러분의 도움이 필요하다!

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. W는 대문자 영어 문자로만 이루어진다. W는 하나 이상의 단어로 복호화할 수 있다. (즉, W는 어떤 단어를 암호화한 결과이다.) W를 복호화해도 단어 AMBIGUOUS이 되지 않는다. (복호화 결과가 모호할 때만 이를 출력한다.)

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ W ≤ 4의 길이.

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ W ≤ 50의 길이.

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

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

마지막 예제 테스트 케이스는 작은 데이터 세트에는 등장하지 않는다는 점에 유의하라.

예제 테스트 케이스 #1과 #2는 문제 설명에서 설명했다.

예제 테스트 케이스 #3에서는 BANANA만이 AOAAAN로 암호화되는 유일한 단어이다.