← 返回题目列表

Codeforces · 2003/C

C. 乌龟和好对

中文机器翻译题面 查看原题

Turtle 给你一个字符串 $$$s$$$,由小写拉丁字母组成。

Turtle 认为一对整数 $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) 是一对令人愉快的整数对,当且仅当存在一个整数 $$$k$$$ 使得 $$$i \le k < j$$$ 并且以下两个条件都成立:

- $$$s_k \ne s_{k + 1}$$$;
- $$$s_k \ne s_i$$$ 或 $$$s_{k + 1} \ne s_j$$$。

此外,Turtle 认为一对整数 $$$(i, j)$$$ ($$$1 \le i < j \le n$$$) 是一个好的整数对,当且仅当 $$$s_i = s_j$$$ 或 $$$(i, j)$$$ 是一个愉快的整数对。

Turtle 想要对字符串 $$$s$$$ 重新排序,以便最大化好对的数量。请帮助他!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 字符串的长度。

每个测试用例的第二行包含一个长度为$$$n$$$的字符串$$$s$$$,由小写拉丁字母组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,重新排序后输出字符串 $$$s$$$,以使好对的数量最大化。如果有多个答案,请打印其中任何一个。

示例

输入 #1

5
3
abc
5
edddf
6
turtle
8
pppppppp
10
codeforces

输出 #1

acb
ddedf
urtlet
pppppppp
codeforces

注意

在第一个测试用例中,$$$(1, 3)$$$ 在重新排序的字符串中是一个很好的对。可以看出,我们无法对字符串进行重新排序,使得好对的数量大于$$$1$$$。 bac 和 cab 也可以是答案。

在第二个测试用例中,$$$(1, 2)$$$、$$$(1, 4)$$$、$$$(1, 5)$$$、$$$(2, 4)$$$、$$$(2, 5)$$$、$$$(3, 5)$$$ 是重新排序的字符串中的好对。 efddd 也可以是答案。