解题思路

本题可以使用贪心算法。

对于字符 $c$，镜像字符为：

$mirror(c) = 'a' + ('z' - c)$

也就是：

题目内容

给定一个仅由小写英文字母组成的字符串 $s$。你可以选择至多一次，对任意一个连续区间 $[l, r]$（$1 \le l \le r \le |s|$）执行如下“镜像”操作：将区间内每个字符 $c$ 替换为 $\text{mirror}(c)$，其中

即有 $\text{'a'} \leftrightarrow \text{'z'}$、$\text{'b'} \leftrightarrow \text{'y'}$、$\text{'c'} \leftrightarrow \text{'x'}$、$\dots$、$\text{'m'} \leftrightarrow \text{'n'}$。

你也可以选择不进行任何操作。请在至多一次操作后，使得到的字符串按字典序尽可能小，并输出该最小结果。

名词解释:

• 字典序：按通常的字母顺序比较字符串，从左到右逐字符比较，先出现更小字符的字符串更小；若一方为另一方前缀，则更短者更小。
• 镜像操作：对区间内每个字符 $c$ 映射为 $\text{mirror}(c) = \text{'a'} + (\text{'z'} - c)$。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 10^5$）表示数据组数。

接下来 $T$ 行，每行一个字符串 $s$，满足 $s$ 仅包含小写英文字母，且 $1 \le |s| \le 10^5$。

保证所有测试中字符串长度之和不超过 $2 \times 10^5$。

输出描述

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

样例1

输入

5
abcxyz
aaaa
zyx
az
b

输出

abccba
aaaa
abc
aa
b

说明

• 样例一：对区间 $[4,6]$ 执行镜像，'$x$' $→$ '$c$', '$y$' $→$ '$b$', '$z$' $→$ '$a$'，得到 "$abccba$"，比不操作的 "$abcxyz$" 更小。
• 样例二：任意包含 '$a$' 的区间镜像都会把 '$a$' 变为 '$z$' 变大，故不操作最优，输出 "$aaaa$"。
• 样例三：整体镜像 "$zyx$" $→$ "$abc$" 为最优。
• 样例四：只镜像末尾 '$z$' $→$ '$a$'，得到 "$aa$" 优于不操作的 "$az$"。
• 样例五：镜像 '$b$' $→$ '$y$' 变大，故不操作最优。