숨겨진 암호

당신의 해킹 실력을 시험할 시간입니다! 당신은 전쟁 중인 적의 암호를 해독하는 임무를 맡았습니다. 다행히 적이 사용하는 암호화 기법을 알아냈는데, 방식은 아주 단순하며 다음과 같습니다. 모든 문자열은 알파벳 대문자로만 이루어져 있습니다.

1. 키 $K$와 평문 $P$가 주어지고, $P$는 한 글자씩 암호화되어 같은 길이의 암호문 $C$가 됩니다.
2. $|K|$를 키 $K$의 길이라고 하면, $C$의 처음 $|K|$개 문자는 $P$의 처음 $|K|$개 문자에 $K$의 각 문자를 더해서 얻습니다. 두 문자를 더한다는 것은 각 문자를 수로 해석하고($A = 0$, $B = 1$, ...) 그 합을 26으로 나눈 나머지를 취하는 것입니다. 즉 $i = 1, \dots, |K|$에 대해 $C_i = (P_i + K_i) \bmod 26$ 입니다. 만약 $|K| > |P|$이면 $K$의 남는 문자는 무시합니다.
3. $P$의 나머지 문자들, 즉 $i > |K|$인 $P_i$는 앞서 만들어진 암호문 문자를 이용해 암호화됩니다. $i = |K| + 1, \dots, |P|$에 대해 $C_i = (P_i + C_{i-|K|}) \bmod 26$ 입니다.

예를 들어 문자열 "STANFORD"를 키 "ACM"으로 암호화하면 다음과 같습니다.

  STA NFORD
+ ACM SVMFA
  ----------
  SVM FAAWD

이제 적의 통신을 읽을 준비가 거의 끝났습니다. 다행히도 팀이 복구한 여러 쌍의 평문과 암호문이 있고, 이들은 모두 같은 키로 암호화되었다는 것이 알려져 있습니다. 적이 사용하는 키를 찾아 주세요. 키는 가장 긴 복구된 평문에 의해 유일하게 결정되므로, 가장 짧은 유효한 키는 유일합니다.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 정수 $N$ ($1 \le N \le 100$)이 적힌 줄로 시작하며, 이는 주어지는 평문과 암호문 쌍의 개수입니다. 이어지는 $N$개의 줄에는 각각 두 문자열 $P$와 $C$가 있으며, 각각 평문과 암호문입니다. $P$와 $C$는 대문자(A-Z)로만 이루어지고 길이가 같으며(최대 100자), 입력은 $N = 0$인 줄로 끝나고 이 줄은 처리하지 않습니다.

각 테스트 케이스마다, 가능한 가장 짧은 키를 한 줄에 출력합니다. 주어진 모든 암호화를 만들어낼 수 있는 키가 존재하지 않으면 Impossible을 출력합니다.