# Message Deciphering

### Output file: crypt.out

Messages can be ciphered (encrypted) by systematically replacing letters of the alphabet by other letters. A simple cipher known as the Caesar cipher replaces each letter in the alphabet by the letter k positions later in the alphabet, where A is considered to follow Z . For example, if k = 6, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, and Z would be replaced by G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, A, B, C, D, E, and F respecively. The message

```   THE FULL MOON RISING IS A BAD SIGN
```
would be ciphered as
```   ZNK LARR SUUT XOYOTM OY G HGJ YOMT
```
The inverse of the cipher is again a Caesar cipher with 26-k replacing k.

Your job as cryptanalist is to decode lines of text that have been encoded with a Ceasar cipher, each using a different unknown value of k. For example, if the input were

```   ZNK LARR SUUT XOYOTM OY G HGJ YOMT
FA NQ AD ZAF FA NQ FTMF UE FTQ CGQEFUAZ
```
the output would be
```   THE FULL MOON RISING IS A BAD SIGN
TO BE OR NOT TO BE THAT IS THE QUESTION
```
(the first line was ciphered with k=6 and the second line with k=12).

Of course there are 26 possible values of k and therefore 26 possible ciphers, so you will have to "guess" by selecting the most probable deciphering. The probability of a particular deciphering can be estimated using the probabilities of the letters it contains. In English, E is the most common letter, with probability 0.127, T is the next more common with probability 0.091, and so on. A complete table of letter probabilities is given below. The probability of a complete line of text can be approximated by the product of the probabilities of the letters it contains.

### Input Specification

The input to your program consists of a line containing a positive integer n, followed by n lines each consisting of of upper case letters and spaces only. Each line is an English phrase or sentence, encrypted with a Caesar cipher with unknown k.

### Output Specification

For each line of input, give the most probable deciphering.

### Sample Input

```2
ZNK LARR SUUT XOYOTM OY G HGJ YOMT
FA NQ AD ZAF FA NQ FTMF UE FTQ CGQEFUAZ
```

### Output for Sample Input

```THE FULL MOON RISING IS A BAD SIGN
TO BE OR NOT TO BE THAT IS THE QUESTION
```

## Probabilities of Letters in English Text

```       Letter     Probability       Letter   Probability
A          .082             N          .067
B          .015             O          .075
C          .028             P          .019
D          .043             Q          .001
E          .127             R          .060
F          .022             S          .063
G          .020             T          .091
H          .061             U          .028
I          .070             V          .010
J          .002             W          .023
K          .008             X          .001
L          .040             Y          .020
M          .024             Z          .001
```