解题思路

从左到右处理字符串。对当前位置 $i$ 的原字符 $c$：

维护两个数组：

$cntLeft[c]$：已经处理完的左侧字符中，最终等于 $c$ 的个数。

$cntRight[c]$：当前位置右侧尚未处理的原字符串中，等于 $c$ 的个数。

题目内容

在蝴蝶乐园里，有一串写着小写字母的标牌。给你一个长度为$n$的字符串 $s$，你需要按从左到右的顺序，依次处理位置 $1$ 到$n$。

当你处理到位置$i$ 时，字符串的前半部分（位置 $1$ 到$i-1$）已经可能被你改过；后半部分（位置 $i+1$ 到 $n$）还没有被处理，仍是原来的字符。

对每个位置$i$，执行以下规则一次：

• 令 $c$表示当前位置 i 的字符（处理这一位之前的字符）；

• 令$x$ 表示在位置$i$ 左侧（位置 $1$ 到 $i-1$）中，字符等于$c$的个数（注意：左侧这些字符已经是处理后的最终字符）；

• 令$y$ 表示在位置$i$右侧（位置$i+1$到 $n$）中，字符等于 $c$ 的个数（注意：右侧这些字符还没被处理，仍是原串字符）；

• 如果$x = y$，就把位置$i$ 的字符改成字典序的下一个字符；也就是：

  • 若 $c$ 是 'z'，则变为 'a'；
  • 否则变为 $c$ 的下一个小写字母；

• 如果$x \ne y$，则位置 $i$ 的字符不变。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $t\ (1 \le t \le 2 \times 10^5)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入一个整数 $n$，表示字符串长度；
• 第二行输入一个长度为$n$ 的字符串 $s$，保证仅由小写英文字母组成。

除此之外，保证单个测试文件的 $n$ 之和不超过 $4 \times 10^5$。

输出描述

对于每一组测试数据，新起一行。输出最终的字符串$s$

样例1

输入

3
1
a
3
aba
3
zzz

输出

b
aca
zaz