No testdata at current.

题目描述

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

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

对于任意一种字母，其在字符串中仅有大写或仅有小写形式

对于任意一种字母(不分大小写)，其都在字符串中出现过

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

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

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

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

【名词解释】

从字符串的第一个字符开始逐个比较，直至发现第一个不同的位置，比较这个位置字符的$ASCII$码，$ASCII$码较小 $('A’<'B’...<'Z’<'a’<...<'z’)$ 的

字符串字典序也较小；如果比较到其中一个字符串的结尾时依旧全部相同，则较短的字符串字典序更小。

输入描述

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

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

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

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

输出描述

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

样例1

输入

5
26
abcdefGHljklmnopqrstuvwxyY
8
CAECGEHG
10
MZbMwEyYdl
20
DTLCOUegMDByFWUrPwBp
19
LKGkheSppLQSsAlmtll

输出

ZabcdefGHljklmnopqrstuywxY
BCADECFGEHGIJKLMNOPQRSTUVWXYZ
ACFGHJKLMNOPQRSTUVXZbMwEYdl
ADHIJKNQSTLCOUVXZеgMDByFUrPwB
BCDFGJNORUVWXYZkheSppQsAlmtll

样例解释

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