题目内容

本题为 AI辅助编程题，可以使用 AI 作答。

称一个字符串为 [完全不协调] ，当且仅当：

现在，给定一个长度为 $n$ 、仅由大小写字母构成的字符串 $s$ 。你需要求解使其变为**「完全不协调」**需要的最少操作轮数 $x$ 。其中，每一轮操作从以下两个方法中选择一个执行：

方法一：任选一个字母(大写或小写)，将其插入到字符串的任意位置(包括开头和未尾)。

方法二：选择一个位于字符串中的字符，将其删除。

然而，小美对数字并不感兴趣，她想知道：通过 $x$ 轮操作能得到的字典序最小的「完全不协调」字符串是什么？

【名词解释】

从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的 ASCII码，ASCII码较小 $('A’<'B’...<'Z’<'a’<...<'z’)$ 的字符串字典序也较小；如果比较到其中一个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。

输入描述

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

第一行输入一个整数 $n(1≦n≦ 10^5)$ ，表示原字符串长度；

第二行输入一个长度为 $n$ 的字符串 $s$ ，仅由大小写字母构成。

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

对于每一组测试数据，新起一行。输出一个字符串，表示 $x$ 轮操作能得到的字典序最小的「完全不协调」字符串。

输入

5
26
abcdefGHIjklmnopqrstuvwxyY
8
CAECGEHG
10
MZbMwEyYdI
20
DTLCOUegMDByFWUrPwBp
19
LKGkheSppLQSsAImtll

输出

ZabcdefGHIjklmnopqrstuvwxY
BCADECFGEHGIJKLMNOPQRSTUVWXYZ
ACFGHJKLMNOPQRSTUVXZbMwEYdI
ADHIJKNQSTLCOUVXZegMDByFUrPwB
BCDFGJNORUVWXYZkheSppQSAImtll

说明

对于第一组测试数据，删除了 $y$ 并在字符串首增加了 $Z$ 。