该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

徐老师研究了一种电报加密算法，加密规则是对于每一个字符，如果是字母，变换成其相应的其后（循环的字母序，即A紧跟在Z的后面）的第4个字母。例如A变成E，a变成e，W变成A，X变成B，Y变成C，Z变成D，解密规则反之。如果不是字母，则不进行变换。特别的，以0结尾则是明文，1结尾则是密文，加密或解密后需要对最后一位进行反转。现在给定明文，请你求出密文，或者给定密文，请你求出明文

Format

Input

第一行一个整数$T(1 \leq T \leq 100)$，表示测试组数

对于每组测试，一行一个字符串$s(1 \leq |s| \leq 10^4)$，表示给定的电报

Output

对于每组测试，输出一个字符串

Samples

1
a0

e1

Limitation

1s, 1024KiB for each test case.