出题人太菜，暂无测试数据。

题目描述

在遥远的过去，某国为了国防安全，设计了一套加密算法。这套加密算法会首先将 26 个英文字母按任意顺序顺时针围成一个环，然后要传输的文本的每个字母都用这个环上的它的下一个字母替换。例如，假设 26 个英文字母排成的环为：qwertyuiopasdfghjklzxcvbnm，那么如果传输的文本为 manwhatcanisay，则加密后的文本为 qsmejsyvsmodsu。我们将这个环称为密钥。

假设你是这个国家敌国的间谍，你截获了对方的一段加密文本（设为 t），但是你不知道加密的密钥。你想要知道：将 t 通过某种密钥还原之后能得到的字典序最小的密文可能是什么？

输入格式

第一行一个正整数 T，表示数据组数。

对于每组数据，第一行一个字符串 t，表示加密后的密文。保证字符串仅包含小写字母。

输出格式

对于每组数据，输出一行一个字符串，表示还原后的字典序最小的明文。

样例

样例输入

3
qsmejsyvsmodsu
abcdefghijklmnopqrstuvwxyz
abcdefghijklmnopqrstuvwxzy

样例输出

abcdebfgbchibj
bcdefghijklmnopqrstuvwxyza
bcdefghijklmnopqrstuvwxyaz

数据范围与提示

• 对于 30% 的数据，1 \le T \le 10, 1 \le |t| \le 10, \sum |t| \le 100；
• 对于 100% 的数据，1 \le T \le 10^4, 1 \le |t| \le 2 \times 10^5, \sum |t| \le 2\times 10^5。