Canadian Computing Competition: 1998 Stage 2, Day 1, Problem 2

Messages can be ciphered (encrypted) by systematically replacing letters of the alphabet with other letters. A simple cipher known as the Caesar cipher replaces each letter in the alphabet with the letter ~k~ positions later in the alphabet, where A is considered to follow Z. For example, if ~k = 6~, ABCDEFGHIJKLMNOPQRSTUVWXYZ would be replaced by GHIJKLMNOPQRSTUVWXYZABCDEF respectively. 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 a cryptanalyst is to decode lines of text that have been encoded with a Caesar 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.

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	.061	V	.010
J	.002	W	.023
K	.008	X	.001
L	.040	Y	.020
M	.024	Z	.001

Input Specification

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

The input will have at most 500 characters of input (including spaces).

Output Specification

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

Note that all the data are generated such that there is only one unique most probable deciphering.

Sample Input

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

Sample Output

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