题目内容

在一个由小写字母组成的字符串上，我们定义每个字母的 镜面字母。对于一个字母 $c$，其镜面字母为 $r(c) = \text{'a'} + (\text{'z'} - c)$，即字母表两端对称的字母：'a' 与 'z' 互为镜面，'b' 与 'y' 互为镜面，以此类推，'m' 与 'n' 互为镜面。

你可以对字符串执行 至多一次 操作：选定一个连续区间（可以为空，即不操作），将区间内的每个字母替换为其镜面字母。

你的目标是经过至多一次操作后，使字符串的字典序尽可能小。请输出此时能得到的字典序最小的字符串。

字典序的定义：按照字母的通常顺序从左向右逐字符比较，第一个不同的字符中字母更小的字符串更小；若一个字符串是另一个的前缀，则更短的字符串更小。

数据范围

• 测试数据组数 $T$ 满足 $1 \le T \le 10^5$。
• 每组字符串的长度不超过 $10^5$。
• 所有字符串的字符总数不超过 $2 \times 10^5$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。接下来 $T$ 行，每行包含一个仅由小写字母组成的字符串。

输出描述

输出 $T$ 行，每行一个字符串，表示在至多一次操作后可得到的字典序最小的字符串。

样例1

输入

1
abc

输出

abc

说明

字符串 abc 中所有字母都在 'a' 到 'm' 之间，替换为镜面字母后会变大。为了字典序最小，不进行任何操作，输出原字符串 abc。

样例2

输入

1
banana

输出

bamana

说明

从左到右寻找第一个替换后能变小的字母，即第一个满足 $s_i \\ge$ 'n' 的字母。

字符串 banana 中第 3 个字母 'n' 满足条件，将其替换为镜面字母 'm'。紧接着的字母 'a' 满足 $s_i \\le$ 'm'，替换后会变大，因此停止操作。最终得到 bamana。

样例3

输入

1
zyx

输出

abc

说明

字符串 zyx 的所有字母均满足 $s_i \\ge$ 'n'。从左往右连续替换：'z' 变为 'a'，'y' 变为 'b'，'x' 变为 'c'，得到 abc，为可能的最小字典序。

样例4

输入

1
hello

输出

helll

说明

第一个满足 $s_i \\ge$ 'n' 的位置是字符串 hello 的第 5 个字母 'o'，将其替换为 'l'。前面的字母均 $\\le$ 'm'，保持不变，结果为 helll。