형의 일기

요즘 안전하게 소통하려는 사람들은 RSA 같은 비대칭 암호 알고리즘을 사용한다. 하지만 우리 형은 그보다 간단한 방법으로 일기를 지킨다. 바로 평문의 각 글자를 알파벳의 다른 글자로 바꾸는 치환 암호인데, 언제나 같은 고정된 거리만큼 밀어서 바꾼다. 이 고정 거리 $d$가 $5$라면 A는 F로, B는 G로, C는 H로 바뀌며, 알파벳의 끝을 넘어가면 다시 처음으로 돌아와 Y는 D로, Z는 E로 바뀐다.

거리 $d$가 고정되어 있고 알려져 있다면 복호화는 쉬울 것이다. 그러나 형은 일기 항목마다 거리를 무작위로 정하므로, 어떤 항목을 읽으려면 먼저 그 항목의 거리 $d$를 알아내야 한다. 이를 위해 나는 영어 문장에서 글자 E가 다른 어떤 글자보다 자주 나온다는 잘 알려진 사실을 이용한다.

암호문에서 가장 자주 나오는 글자가 평문의 글자 E에 해당한다고 가정하여 거리 $d$를 계산하는 프로그램을 만들어 줄 수 있는가? 물론 복호화된 문장도 함께 보고 싶다.

첫째 줄에 테스트 케이스의 개수 $c$ $(1 \le c \le 100)$가 주어진다. 이어지는 $c$개의 줄에는 각각 일기 항목이 정확히 하나씩 주어진다. 일기 항목은 대문자 알파벳(A–Z)과 공백만으로 이루어지며, 각 항목의 길이는 공백을 포함하여 최대 $1000$자이다.

각 테스트 케이스마다 한 줄에 가능한 가장 작은 거리 $d$ $(0 \le d \le 25)$와 복호화된 문장을 함께 출력한다. 위 규칙에 맞는 거리가 둘 이상이어서 복호화가 불가능하다면, 대신 NOT POSSIBLE을 출력한다. 공백은 암호화되지 않는다.