1567.E - 密码破解

## 题目描述

密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律，常应用于编制密码以保守通信秘密的。从古代传递情报道现在电脑的通信一直扮演着一个十分重要的角色。相信你一定听说过「凯撒密码」，它属于是一种替换密码。一种凯撒密码的替换方式是 $A \rightarrow D,B \rightarrow E,...,X \rightarrow A,Y \rightarrow B, Z \rightarrow C$。以数学的方式来说，我们让$A=0,B=1,...,Z=25$，使用密钥 $x$ 加密明文 $a$ 得到的密文就是 ：

$E_x(a)=(a+x) \ mod \ 26$

以现在的计算机技术，凯撒密码是很容易破解的，即使我们不知道其中用来加密的密钥 $x$ 的值，我们依然可以借助计算机强大的算力通过频率分析方法将其暴力解出。当密文长度足够大的情况下，可以先分析密文中每个字母出现的频率，然后将这一频率与正常情况下的该语言字母表中所有字母的出现频率做比较。例如在英语中，正常明文中字母 $E$ 和 $T$ 出现的频率特别高，而字母 $Q$和 $Z$ 出现的频率特别低，而在法语中出现频率最高的字母是 $E$ ，最低的是 $K$ 和 $W$。可以通过这一特点，分析密文字母出现的频率，可以估计出正确的密钥 $x$。

这里我们要介绍一种改良版的凯撒密码。现在你有一组密钥 $x_1 x_2 ... x+l$，要加密的信息 $a_1 a_2 a_n$ 得到密文 $c_1 c_2 ... c_n$。我们拿第一个密钥的字母 $x_1$ 加密 $a_1$，拿第二个密钥的字母 $x_2$ 加密 $a_2$，......。如果密钥用完了，我们就拿前面得到的密文来用，也就是拿 $c_1$ 来加密 a$_{l+1}$。

$c_i = \begin{matrix}  a_i+x_i \ mod \ 26 , i \le l \\ a_i + c_{i-l} \ mod \ 26 , i>l \end{matrix}$

举例来说，用密钥 $ACM$加密明文 $VAMRI$ 变为密文 $VCYMK$

$\frac{ \begin{matrix}& V & A & M & R & I \\+ & A & C & M & V & C \end{matrix} }{ \begin{matrix} & V & C & Y & M & K  \end{matrix} }$

现在，给你几组用同样的密钥加密的明文密文配对，请你写程序来破解出密钥。

## 输入格式

第一行一个正整数 $T$，代表测试数据的组数。

每组测试数据在第一行给出一个正整数 $N$，代表有几对明文密文配对。

接下来 $N$ 行每行给出两个以空格分隔且只由大写字母组成的字符串 $s_1,s_2$，前面的代表明文，后面的是加密后的密文。

- $1 \le T \le 200$
- $1 \le N \le 10$
- $1 \le \left| s_1 \right| = \left| s_2 \right| \le 300$

## 输出格式

对于每组输入在一行中输出一个字符串，代表能够将 $N$ 组明文分别加密成对应密文的密钥。

如果有多种可能的密钥，请输出最短的那个。

如果没有任何符合的密钥，请输出 "`-`"。

## 输入
```in1
2
1
VAMRI VCYMK
2
CAKES DEOHW
```

## 输出
```out1
ACM
BEE
```

## 提示