이중 암호

앨리스와 여동생 아이린은 서로 자주 이메일을 주고받는다. 도청을 걱정한 두 사람은 편지를 비밀로 유지하기 위해 메시지를 두 단계로 암호화한다. 먼저 알파벳이 아닌 문자를 모두 제거하고 모든 글자를 대문자로 바꾼다(이 결과를 변형 평문(modified plaintext) 이라고 부른다). 그다음 아래 두 단계를 수행한다.

1. 각 글자를 알파벳에서 $s$ 칸 뒤의 글자로 바꾼다($1 \le s \le 25$). 이를 $s$ 만큼의 시프트라고 부른다. 알파벳은 순환하므로, 예를 들어 $s = 2$ 일 때 Y 는 A 가 되고 Z 는 B 가 된다.
2. 1단계의 결과를 $m$ 글자씩 묶어($5 \le m \le 20$) 각 묶음 안의 글자 순서를 뒤집는다. 전체 길이가 $m$ 으로 나누어떨어지지 않으면, 마지막 $k$ 개($k < m$)의 글자만 뒤집는다.

예를 들어 $s = 2$, $m = 6$ 이라고 하자. 평문이 Meet me in St. Louis, Louis. 라면, 알파벳이 아닌 문자를 제거하고 대문자로 바꾼 변형 평문은 다음과 같다.

MEETMEINSTLOUISLOUIS

각 글자를 2만큼 시프트하면 중간 결과는 다음과 같다.

OGGVOGKPUVNQWKUNQWKU

마지막으로 6글자씩 묶어 각 묶음을 뒤집으면 다음과 같다(마지막 두 글자가 마지막 묶음을 이룬다).

GOVGGOQNVUPKWQNUKWUK

관례에 따라 결과를 5글자씩 끊어 적으면 암호문은 다음과 같다.

GOVGG OQNVU PKWQN UKWUK

암호문을 가로챘을 때 $s$ 와 $m$ 을 알아내는 것은 그리 어렵지 않으며, 크립(crib), 즉 변형 평문에 들어 있는 한 단어를 알고 있으면 더욱 쉬워진다. 위 예시에서는 LOUIS 가 크립이다. 이 문제에서는 암호문과 크립이 주어졌을 때 $s$ 와 $m$ 을 찾아야 한다.

입력은 여러 개의 문제 인스턴스로 이루어진다. 첫 줄에는 문제 인스턴스의 개수를 나타내는 양의 정수가 주어진다.

각 인스턴스의 입력은 여러 줄로 구성된다. 첫 줄에는 암호문의 글자 수와 같은 정수 $n$($20 \le n \le 500$)이 주어진다. 이어지는 줄들에는 암호문이 주어지며, 모두 대문자이고 5글자씩 묶여 하나의 공백으로 구분된다(마지막 묶음은 5글자보다 적을 수 있다). 한 줄에는 10개의 묶음이 주어지되, 암호문의 마지막 줄만은 그보다 적을 수 있다. 암호문의 마지막 줄 다음 줄에는 크립이 주어진다. 크립은 4자 이상 10자 이하의 대문자로 이루어진 한 단어이다.

크립을 만들어 내는 암호 키인 두 정수 $s$ 와 $m$ 을 한 줄에 공백 하나로 구분하여 출력한다. 여기서 $s$ 는 시프트 양이고 $m$ 은 뒤집는 묶음의 크기이다. 해가 여러 개이면 $s$ 가 가장 작은 것을 출력한다. $s$ 가 같은 해가 여러 개이면 $m$ 이 가장 작은 것을 출력한다. 그러한 $s$ 와 $m$ 이 존재하지 않으면 Crib is not encrypted. 를 출력한다.