题目内容

给定一个长度为 $n$ 的字符串 $s$，仅由小写字母组成。现在从左至右依次处理每个字符。当处理到第 $i$ 个位置（从 $1$ 开始）时，记：

• 左侧部分：位置 $1$ 到 $i-1$ 已经处理完毕的字符（即最终的字符）；
• 右侧部分：位置 $i+1$ 到 $n$ 的原始字符；
• 当前字符 $c$：原始串中位置 $i$ 的字符。

设 $L$ 为左侧部分中等于 $c$ 的字符个数，$R$ 为右侧部分中等于 $c$ 的字符个数。

若 $L = R$，则将该位置的字符替换为 $c$ 的下一个字母（字母表视为循环，即 'z' 的下一个字母为 'a'），否则保持不变。将最终确定的字符（可能是 $c$ 或变换后的字符）作为该位置的永久结果，并将其计入左侧部分，用于后续位置的处理。按照上述规则处理完所有位置后，输出得到的完整字符串。

数据范围：测试用例数量 $t$ 满足 $1 \le t \le 2 \times 10^5$，所有测试用例的字符串长度之和不超过 $4 \times 10^5$。

输入描述

第一行包含一个整数 $t$，表示测试用例的数量。接下来依次给出每组数据。每组数据包含两行：第一行包含一个整数 $n$（$n \ge 1$），表示字符串的长度；第二行包含一个长度为 $n$ 的字符串 $s$，仅由小写字母构成。

输出描述

对于每组测试数据，输出一行，包含处理完成后得到的最终字符串。

样例1

输入

1
1
z

输出

a

说明

字符串长度为 1，仅包含字符 z。处理第 1 个字符时，左侧已处理的最终字符为空，因此 $L = 0$；右侧的原始字符在移除当前字符后也为空，因此 $R = 0$。因为 $L = R$，当前字符 z 被替换为下一个字母，即 a。最终结果为 a。

样例2

输入

1
5
ababa

输出

abbba

说明

初始字符串为 ababa。初始时右侧计数：a 出现 3 次，b 出现 2 次。左侧计数全为 $0$。

• 处理第 1 个字符 a：从右侧移除后右侧 a 剩 2 次；左侧 $L=0$，右侧 $R=2$，$L eq R$，保持为 a，左侧 a 计数变为 1。
• 处理第 2 个字符 b：右侧 b 剩 1 次；$L=0$，$R=1$，不等，保持 b，左侧 b 计数变为 1。
• 处理第 3 个字符 a：右侧 a 剩 1 次；$L=1$（左侧已有 1 个 a），$R=1$，相等，替换为下一个字母 b，左侧 b 计数变为 2。
• 处理第 4 个字符 b：右侧 b 剩 0 次；$L=2$，$R=0$，不等，保持 b，左侧 b 计数变为 3。
• 处理第 5 个字符 a：右侧 a 剩 0 次；$L=1$，$R=0$，不等，保持 a。

最终得到的字符串为 abbba。

样例3

输入

2
3
aba
4
zzzz

输出

aca
zzzz

说明

共有 2 组测试数据。

第一组：s = "aba"。初始右侧 a 出现 2 次，b 出现 1 次。

• 处理第 1 个字符 a：右侧 a 减为 1；$L=0$，$R=1$，不等，保持 a。
• 处理第 2 个字符 b：右侧 b 减为 0；$L=0$，$R=0$，相等，替换为 c。
• 处理第 3 个字符 a：右侧 a 减为 0；$L=1$，$R=0$，不等，保持 a。 结果为 aca。

第二组：s = "zzzz"。初始右侧 z 出现 4 次。处理每个 z 时，右侧计数依次变为 3、2、1、0，左侧计数依次变为 0、1、2、3。在任意位置均有 $L eq R$（0≠3, 1≠2, 2≠1, 3≠0），因此不发生替换。结果为 zzzz。