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

假设你是这个国家敌国的间谍，你截获了对方的一段加密文本（设为 ），但是你不知道加密的密钥。你想要知道：将

通过某种密钥还原之后能得到的字典序最小的密文可能是什么？ 输入格式

第一行一个正整数

，表示数据组数。

对于每组数据，第一行一个字符串

，表示加密后的密文。保证字符串仅包含小写字母。 输出格式

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

3

qsmejsyvsmodsu

abcdefghijklmnopqrstuvwxyz

abcdefghijklmnopqrstuvwxzy

样例输出

abcdebfgbchibj

bcdefghijklmnopqrstuvwxyza

bcdefghijklmnopqrstuvwxyaz