Problem 1016 --Enigma

1016: Enigma

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 37  Solved: 8
[Submit][Status][Web Board][Creator:]

Description


二战时期,德军使用了一套名为Enigma的密码系统,是一种基于字符映射的密码系统。它的工作原理如下:

使用者从键盘按下一个字母后,字母会先经过三个可以转动的轮盘,称为转子,每个转子就是一个字符映射表。如:

输入

A

B

C

D

E

输出

D

E

A

B

C

一个转子的输出作为下一个转子的输入。当经过第三个转子后,输出会被送入到一个反射器。反射器和转子一样,区别在于不能转动,且映射是对称的,即如果输入c1会输出c2,那么输入c2将输出c1。经过反射器后,字母会依次反向进入三个转子,并最终显示在显示盘上。至此算完成了一个字母的加密。当加密下一个字母时,第一个转子会转动一格,转子的转动代表着映射表发生变化。如上表在转动后将变成

输入

A

B

C

D

E

输出

E

A

B

C

D

当转子转动一周再次回到初始位置时,会带动第二个转子转动一格,同理第二个转动一周后,会带动第三个转子转动。(第三个转子本题中不考虑。)

本题中的三个转子和反射器的结构如下:

转子AQAZWSXEDCRFVTGBYHNUJMIKOLP

转子BQWERTYUIOPASDFGHJKLZXCVBNM

转子CQETUOADGJLZCBMWRYIPSFHKXVN

反射器:ZYXWVUTSRQPONMLKJIHGFEDCBA

使用时三个转子也可拆卸自由调节顺序,也就是说加密操作前的初始状态会有26­­*26*26*3!种。我们用6位字母来记录初始状态,并称为密钥。1-3位记录三个的转子的排列顺序(如BAC表示B转子放在最靠近键盘的位置)。4-6位记录三个转子的初始位置(如XYZ表示最靠近键盘的转子初始位置在X上)。

现在提供你一串密文和密钥,请给出它的原文。


Input

第一行输入整数T(1<=T<=1000),代表测试用例的数量。

接下来每个用例由两行组成,第一行由六个大写字母组成,表示密钥。第二行为待解密字符串,由大写字母组成,长度不超过6666。

Output

每一行输出解密后的明文。

Sample Input

1
ABCXYZ 
ZDBSF

Sample Output

HELLO

HINT

Source

[Submit][Status]