Дневник моего брата
В наше время люди, стремящиеся к безопасному общению, используют асимметричные алгоритмы шифрования, такие как RSA. Однако мой старший брат предпочитает более простой метод шифрования для своих дневниковых записей. Он применяет шифр подстановки, где каждая буква открытого текста заменяется другой буквой алфавита. Расстояние между исходной и зашифрованной буквой фиксировано. Если это фиксированное расстояние d равно 5, то A заменяется на F, B на G, C на H, ..., Y на D, Z на E.
С известным фиксированным расстоянием d расшифровка была бы довольно простой. Но мой брат использует случайные расстояния для каждой записи в дневнике. Чтобы расшифровать его записи, мне приходится угадывать расстояние d для каждой из них. Я использую известное явление, что буква E встречается в английских текстах чаще других. Можешь ли ты написать программу, которая определяет расстояние d, исходя из того, что наиболее часто встречающаяся буква в зашифрованном тексте соответствует букве E в открытом тексте? Конечно, меня интересует и расшифрованный текст.
Входные данные
Входные данные состоят из нескольких тестов c (1 ≤ c ≤ 100). Каждый тест представлен одной строкой, содержащей запись из дневника. Записи содержат только заглавные буквы (A-Z) и пробелы. Каждая запись состоит не более чем из 1000 зашифрованных символов (включая пробелы).
Выходные данные
Для каждого теста выведите строку, содержащую наименьшее возможное расстояние d (0 ≤ d ≤ 25) и расшифрованный текст. Если расшифровка невозможна из-за наличия нескольких расстояний, соответствующих указанным правилам, выведите NOT POSSIBLE. Пробелы не шифруются.