## 题目背景

普莱费尔（Playfair）密码是一种基于字母对的古典密码。它使用一个 的字母矩阵作为密钥对明文进行加密。

你想要破译若干段经过普莱费尔密码加密后的密文，你觉得人工破译有些耗费时间，你想编写一个程序来帮助你破译密码。

## 题目描述

普莱费尔密码的加密规则如下：

1. 将明文中的字母全部转为大写，再将所有字母 `J` 统一替换为字母 `I`。

2. 遵循以下步骤将明文划分为若干字母对 ：

① 从左到右将明文按顺序划分为若干个字母对（每对两个字母）。

② 若存在两个字母相同的字母对（例如 `AA`），则取最左侧的一对，在第一个字母后插入一个填充字母：

- 若该字母不是 `X`，则插入 `X`；

- 若该字母是 `X`，则插入 `Q`。

插入后回到 ① ，直到不存在两个字母相同的字母对。

③ 若最后剩下单个字母（即无法形成一对），则在其后补一个填充字母：

- 若该字母不是 `X`，则补 `X`；
- 若该字母是 `X`，则补 `Q`。

经过以上步骤后，明文被划分为若干个字母对 。

3. 对每一个字母对 ，根据矩阵规则加密，在本题中秘钥矩阵固定给出：

- 同行规则：若 在矩阵中对应的位置在同一行，则将它们分别替换为其右边的字母（行内循环），第 列的右边为第 列。

- 同列规则：若 在矩阵中对应的位置在同一列，则将它们分别替换为其下方的字母（列内循环），第 行的下方为第 行。

- 矩形规则：若 在矩阵中对应的位置在不同的行和列，则分别替换为与之同一行但位于另一字母所在列的字母。

秘钥矩阵：

```
P L A Y F
I R B C D
E G H K M
N O Q S T
U V W X Z
```

4. 将所有加密后的字母依次拼接，即得到密文。

现在有若干段仅由大写字母组成的明文被加密，给出密文，你需要编写程序来获得明文，若存在多种满足条件的明文，请输出任意一种。

- 第一行包含一个整数  ，表示测试数据的组数。

- 接下来  行，每行包含一个仅由大写字母组成的字符串，表示一段密文。

- 保证至少存在一个明文对应给出密文，且所有字符串长度之和不超过 。

- 输出共  行。

- 第  行输出第  组数据解密得到的明文。

- 如果存在多种可能的明文，输出任意一种即可。

3
KGYVRV
NMTN
EBIMQMGHVRIRONKGODKUKNNZEF

HELLO
TEST
HIDETHEGOLDINTHETREESTUMP

### 样例说明

在样例一中，`HELLO` 和 `HELXLO` 都满足要求。