변형 플레이페어 암호

암호화는 평문에서 대응하는 암호문을 만드는 과정이다. 그 방법 중 하나가 플레이페어 암호다. 이 암호는 1850년대에 찰스 휘트스톤이 고안했고, 이름은 암호를 열심히 알린 스코틀랜드 과학자 라이언 플레이페어에게서 왔다. 많은 치환 암호와 달리 플레이페어 암호는 글자를 하나씩 암호화하지 않는다. 두 글자를 묶은 다이그래프 단위로 암호화한다.

암호화에는 두 당사자만 아는 비밀 키로 만든 $5 \times 5$ 격자를 쓴다. 격자는 이렇게 만든다. 키의 글자를 왼쪽 위 칸부터 행 방향으로 한 칸에 하나씩 적되, 이미 적은 글자는 건너뛴다. 키를 다 적으면 아직 쓰지 않은 알파벳을 순서대로 남은 칸에 채우고, I와 J는 한 칸을 같이 쓴다. 예를 들어 키가 "ECNA PROGRAMMING CONTEST"라면 격자는 다음과 같다.

다이그래프는 다음 규칙으로 암호화한다.

1. 두 글자가 같은 행에 있으면 각각 바로 오른쪽 글자로 바꾼다. 행의 오른쪽 끝에서는 같은 행의 첫 칸으로 돌아간다. 위 격자에서 평문 다이그래프 DS는 FB가 되고, AP는 PE가 된다.
2. 두 글자가 같은 열에 있으면 각각 바로 아래 글자로 바꾼다. 열의 맨 아래에서는 같은 열의 첫 칸으로 돌아간다. PF는 IU(또는 JU)가 되고, WO는 CS가 된다.
3. 그 밖의 경우에는 첫 글자를 자기 행을 따라 두 번째 글자의 열까지 밀고, 두 번째 글자도 같은 방식으로 민다. 이렇게 도착한 두 글자가 암호문이다. 원래 다이그래프를 격자 안 직사각형의 두 꼭짓점으로 보면, 나머지 두 꼭짓점의 글자로 바꾸는 셈이다. TU는 FH가 되고, UT는 HF, ZC는 WP가 된다.

다이그래프에 같은 글자가 두 번 들어가면 어떻게 할까. 원래 플레이페어 암호는 두 글자 사이에 'X'를 끼워 넣고 암호화를 이어 간다. 평문의 글자 수가 홀수면 맨 뒤에도 'X'를 하나 붙인다. 그래서 평문 "OOPS"는 먼저 다이그래프 "OX", "OP", "SX"가 되고, 위 격자에서 "GWICBW"로 암호화된다. 평문 "POOS"는 두 'O'가 한 다이그래프에 들어가지 않으므로 글자를 덧붙일 필요가 없다.

이 문제에서는 플레이페어 암호를 한 가지만 바꾼다. 끼워 넣는 글자로 늘 'X'를 쓰는 대신, 처음 끼워 넣을 때는 'A', 그다음에는 'B'를 쓰는 식으로 순서대로 진행한다. 다만 'J'는 끼워 넣는 글자로 쓰지 않고 'I' 다음에는 곧바로 'K'로 넘어간다. 'Z'까지 쓰면 다시 'A'로 돌아간다. 끼워 넣을 글자가 같은 글자 두 개짜리 다이그래프를 만든다면 그 글자는 건너뛰고 다음 글자를 쓴다. 이 규칙에서 "OOPS"는 다이그래프 "OA", "OP", "SB"가 되고, 평문 "AABCC"는 "AB", "AB", "CD", "CE"가 된다.

키와 평문이 주어지면 대응하는 암호문을 구하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 개수 $n$이 주어진다. 각 테스트 케이스는 두 줄로 이루어지며, 첫 줄은 키, 둘째 줄은 암호화할 평문이다. 두 줄 모두 대문자와 소문자, 공백, 알파벳이 아닌 문자를 포함할 수 있고, 공백과 알파벳이 아닌 문자는 무시한다. 키와 평문에 'j'와 'J'는 나오지 않는다.

각 테스트 케이스마다 한 줄에 Case k: 를 출력하고 이어서 암호문을 출력한다. $k$는 1부터 시작하는 테스트 케이스 번호다. 암호문은 공백 없이 대문자로만 쓰고, 'J' 대신 항상 'I'를 쓴다.