비제네르 암호

블랙 위도우와 호크아이는 닉 퓨리를 위한 깜짝 생일 파티를 계획하면서, 닉이 메시지를 읽지 못하도록 암호로 대화하기로 한다. 이들이 사용하는 것은 비제네르 암호(Vigenère cipher)로, 1553년 조반 바티스타 벨라소가 처음 기술한 간단한 다중 문자 치환 암호이다.

비제네르 암호는 카이사르 암호를 일반화한 것이다. 카이사르 암호에서는 모든 글자를 같은 크기만큼 이동시킨다. 예를 들어 이동량이 3이면 A는 D, B는 E, Y는 B가 된다(알파벳 끝을 지나면 처음으로 돌아온다). 비제네르 암호는 이동량이 서로 다른 여러 개의 카이사르 암호를 차례대로 적용한다.

암호화하려면 먼저 키워드를 정하고, 평문과 길이가 같아질 때까지 키워드를 반복한다. 평문이 ATTACKATDAWN이고 키워드가 LEMON이라면 반복된 키는 다음과 같다.

평문:   ATTACKATDAWN
키워드: LEMONLEMONLE

각 평문 글자는 같은 위치에 놓인 키워드 글자가 나타내는 만큼 이동한다. 한 글자의 이동량은 알파벳에서의 위치이다(A = 0, B = 1, …, Z = 25). 따라서 키워드 글자 L은 11만큼 이동시켜 A는 L, B는 M이 되고, Z를 지나면 다시 A로 돌아온다. 키워드 글자 E는 4만큼 이동시키므로 T는 X가 된다.

정리하면 평문 글자를 $P_0 P_1 \dots$, 반복된 키워드 글자를 $K_0 K_1 \dots$라 할 때, 각 암호문 글자는 위의 알파벳 위치를 이용해 $C_i = (P_i + K_i) \bmod 26$으로 계산된다.

이 규칙에 따라 ATTACKATDAWN을 키워드 LEMON으로 암호화하면 LXFOPVEFRNHR이 된다.

비제네르 암호로 메시지를 암호화하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다($T < 100$).

다음 $T$개의 줄에는 각각 하나의 테스트 케이스가 주어진다. 각 줄에는 키워드와 평문이 공백 하나로 구분되어 주어진다. 두 문자열은 모두 대문자 A부터 Z까지로만 이루어져 있다(숫자, 문장 부호, 공백 등은 이미 제거되어 있다).

각 테스트 케이스마다 다음 형식으로 한 줄씩 출력한다.

Ciphertext: <암호문>

여기서 <암호문>은 주어진 키워드로 비제네르 암호를 적용해 평문을 암호화한 결과이다.