← 返回题目列表

Codeforces · 2047/B

B. 替换字符

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

给你一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含小写英文字母。

您必须执行以下操作一次:

- 选择任意两个索引 $$$i$$$ 和 $$$j$$$ ($$$1 \le i, j \le n$$$)。您可以选择 $$$i = j$$$。
- 设置 $$$s_i := s_j$$$。

你需要最小化$$$s$$$的不同排列$$$^\dagger$$$的数量。在执行一次操作后输出具有最少数量的不同排列的任何字符串。

$$$^\dagger$$$ 字符串的排列是将其字符排列成任意顺序。例如,“bac”是“abc”的排列,但“bcc”不是。

输入

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

每个测试用例的第一行包含 $$$n$$$ ($$$1 \le n \le 10$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的第二行包含长度为$$$n$$$的$$$s$$$。该字符串仅包含小写英文字母。

输出

对于每个测试用例,在应用一次操作后输出所需的$$$s$$$。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

6
3
abc
4
xyyx
8
alphabet
1
k
10
aabbccddee
6
ttbddq

输出 #1

cbc
yyyx
alphaaet
k
eabbccddee
tttddq

注意

在第一个测试用例中,我们可以通过一次操作获得以下字符串:“abc”、“bbc”、“cbc”、“aac”、“acc”、“aba”和“abb”。

字符串“abc”有 $$$6$$$ 不同的排列:“abc”、“acb”、“bac”、“bca”、“cab”和“cba”。

字符串“cbc”有 $$$3$$$ 不同的排列:“bcc”、“cbc”和“ccb”,这是所有可获得的字符串中最低的。事实上,除了“abc”之外的所有可用字符串都有 $$$3$$$ 排列,因此它们中的任何一个都会被接受。