GCPC11F - Diary

Nowadays, people who want to communicate in a secure way use asymmetric encryption algorithms such as RSA. However, my older brother uses another, simpler encryption method for his diary entries. He uses a substitution cipher where each letter in the plaintext is substituted by another letter from the alphabet. The distance between the plaintext letter and the encrypted letter is fixed. If we would define this fixed distance d to 5, A would be replaced by F, B by G, C by H ... Y by D, Z by E.

With a fixed and known distance d the decryption would be somewhat simple. But my brother uses random distances for each of his diary entries. To decrypt his diary I have to guess the distance d for each entry. Thus, I use the well known phenomenon that the letter E is used more often in English words than other letters. Can you write a program for me that calculates the distance d based on the fact that the most used letter in the encrypted text corresponds to the letter E in plaintext? Of course, I am interested in the decrypted text, too.

Input

The input consists of several test cases c that follow (1 ≤ c ≤ 100). Each test case is given in exactly one line containing one diary entry. Diary entries only use upper case letters (A-Z) and spaces. Each diary entry consists of at most 1000 encrypted letters (including spaces).

Output

For each test case, print one line containing the smallest possible distance d (0 ≤ d ≤ 25) and the decrypted text. If the decryption is not possible because there are multiple distances conforming to the rules above, print NOT POSSIBLE instead. Spaces are not encrypted.

Example

Input:
4
RD TQIJW GWTYMJWX INFWD JSYWNJX ZXJ F XNRUQJ JSHWDUYNTS YJHMSNVZJ
THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG
XVIDRE TFCCVXZRKV GIFXIRDDZEX TFEKVJK UVTIPGKZFE
XVIDRE TFCCVXZRKV GIFXIRDDZEX TFEKVJK

Output:
5 MY OLDER BROTHERS DIARY ENTRIES USE A SIMPLE ENCRYPTION TECHNIQUE
10 JXU GKYSA RHEMD VEN ZKCFI ELUH JXU BQPO TEW
17 GERMAN COLLEGIATE PROGRAMMING CONTEST DECRYPTION
NOT POSSIBLE

Added by:Adrian Kuegel
Date:2011-07-05
Time limit:0.407s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Author: Tobias Werth)

hide comments
2017-12-01 06:51:05
cake walk !!!
2017-09-02 19:17:02
Finally AC after ifelsing my way out of 1-2 char cases.
2016-06-20 12:51:04
one of the most irritating problems i have ever come across :/ never knew one can brainf**k us even while using c++ ;)
2016-02-09 07:29:21 minhthai
wow, simple but very easy to make mistake
2015-04-30 17:33:39 Dushyant Singh
Distance cannot be negative and it is also not always less than 13. It is 0 ≤ d ≤ 25. Comments are misleading.
2014-11-01 21:47:47 Angel Gonzalez
You should've specified the distance is meant to be calculated in only one direction (From right to left). Therefore distance from A to E is 22 not 4. Many silly WA's because of that. Not to mention the fact that the problem states : "calculate de min distance" leads to many misinterpretations.

Last edit: 2014-11-01 21:51:02
2014-08-12 17:29:37 Sahil Dua
Easy job in Python. Time limit isn't a problem at all! Just do what strikes your brain just after reading the statement!
2013-12-28 07:14:33 jiglipufff
10 attempts n finally the GREEN signal :)
2013-07-04 03:18:25 Arianto Wibowo
@nikoo28
finally AC, was printing 26 EER ....
2013-07-01 20:05:46 Vishal Sharma
dont know why but getting wa again and again what is the output of single space or newline as input NOT POSSIBLE OR 0
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.