CF2003C.Turtle and Good Pairs

海龟给你一个由小写字母组成的字符串 $s$。

他认为，如果一对整数 $(i, j)$（其中 $1 \le i < j \le n$）满足以下条件，则称其为「愉快对」：

1. 存在一个整数 $k$，满足 $i \le k < j$，而且：
   • $s_k \ne s_{k + 1}$；
   • $s_k \ne s_i$ 或 $s_{k + 1} \ne s_j$。

同时，如果一对整数 $(i, j)$（其中 $1 \le i < j \le n$）是「愉快对」或者 $s_i = s_j$，那么它就是「好对」。

海龟想重新排列字符串 $s$，以使「好对」的数量最大化。请帮他实现这一目标。

输入包括多个测试用例。第一行给出测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是每个测试用例的具体内容。

对于每个测试用例，第一行是一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示字符串的长度。

接下来的一行是一个由小写字母组成的字符串 $s$，长度为 $n$。

保证所有测试用例中的字符串长度之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个重新排列后的字符串 $s$，使得「好对」的数量最大化。如果存在多个解，可以输出其中任意一个。

数据范围与示例

对于第一个测试用例，例如，重新排列后的字符串中 $(1, 3)$ 是「好对」。你可以发现无法进一步增加「好对」的数量。bac 和 cab 也是有效答案。

在第二个测试用例中，重新排列后的字符串中有多个「好对」，例如 $(1, 2)$、$(1, 4)$、$(1, 5)$、$(2, 4)$、$(2, 5)$ 和 $(3, 5)$。efddd 也是一个符合条件的答案。

本翻译由 AI 自动生成