Susie and Calvin are classmates. Calvin would like to be able to pass notes to Susie in class without their teacher or other classmates knowing what they are talking about, just in case the notes fall into the wrong hands. Calvin has devised a system to encrypt his messages.
Calvin only passes one word to Susie each time, and that word consists of only uppercase letters, because Calvin is so excited to talk to Susie. Each word is encrypted as follows:
- Calvin assigns a number to each letter based on the letter's position in the alphabet, where
A
= ,B
= , ...,Z
= . - For every letter in the word, Calvin determines the encrypted value of the letter by summing the values of the 1 or 2 letter(s) that are adjacent to that letter in the word. He takes that sum modulo , and this is the new value of the letter. Calvin then converts the value back to an uppercase letter based on positions in the alphabet, as before.
- The encrypted word is determined by encrypting every letter in the word using this method. Each letter's encryption is based only on the letters from the original unencrypted message, and not on any letters that have already been encrypted.
Let's take a look at one of the notes Calvin is writing for Susie. Since Calvin is always hungry, he wants to let Susie know that he wants to eat again. Calvin encrypts the word SOUP
as follows:
S
= ,O
= ,U
= , andP
= .- Calvin encrypts each letter based on the values of its neighbor(s):
- First letter: .
- Second letter: .
- Third letter: .
- Fourth letter: .
- The values correspond to the letters
OMDU
, and this is the encrypted word that Calvin will write on the note for Susie.
It is guaranteed that Calvin will not send Susie any words that cannot be decrypted at all. For example, Calvin would not send Susie the word APE
, since it does not have any valid decryptions. (That is, there is no word that Calvin could have encrypted to APE
.)
However, Calvin's system is not perfect, and some of the words he sends Susie can actually be decrypted to multiple words, creating ambiguity! For example, BCB
can be decrypted to ABC
or CBA
, among other possibilities.
Susie pulled another all-nighter yesterday to finish school projects, and she is too tired to decrypt Calvin's messages. She needs your help!
Input Specification
The first line of the input gives the number of test cases, . test cases follow. Each case is a single line that contains a string of uppercase letters: an encrypted word that Calvin has sent.
Output Specification
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from ) and y
is the decrypted word, or AMBIGUOUS
if it is impossible to uniquely determine the decrypted word.
Limits
For all subtasks,
- .
- consists of only uppercase English letters.
- is decryptable to one or more words. (That is, is the result of an encryption of some word.)
- does not decrypt to the word
AMBIGUOUS
. (You will only output that when the decryption is ambiguous.)
For of the available marks,
the length of .
For the remaining of the available marks,
the length of .
Sample Input
3
OMDU
BCB
AOAAAN
Sample Output
Case #1: SOUP
Case #2: AMBIGUOUS
Case #3: BANANA
Note that the last sample case would not appear in the Small dataset.
Sample Cases #1 & #2 were explained in the problem statement.
In Sample Case #3, BANANA
is the only word that encrypts to AOAAAN
.
Comments