如果字符串中出现的所有字符出现相同的次数,我们称该字符串为平衡字符串。例如,“coder”、“appall”和“ttttttt”是平衡的,而“wowwow”和“codeforces”则不是。
给你一个字符串$$$s$$$,长度为$$$n$$$,由小写英文字母组成。找到一个由小写英文字母组成的、长度与 $$$n$$$ 相同的平衡字符串 $$$t$$$,并且在尽可能少的位置上与字符串 $$$s$$$ 不同。换句话说,使得 $$$s_i \ne t_i$$$ 的索引 $$$i$$$ 的数量应该尽可能小。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 字符串 $$$s$$$ 的长度。
第二行包含长度为$$$n$$$的字符串$$$s$$$,由小写英文字母组成。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,打印字符串 $$$s$$$ 和平衡字符串 $$$t$$$ 可以不同的最小位置数,后跟这样的字符串 $$$t$$$。
如果有多个解决方案,请打印其中一个。可以证明,至少有一个平衡弦总是存在的。
示例
输入 #1
4 5 hello 10 codeforces 5 eevee 6 appall
输出 #1
1 helno 2 codefofced 1 eeeee 0 appall
注意
在第一个测试用例中,给定的字符串“hello”不平衡:字母“h”、“e”和“o”在其中出现一次,而字母“l”出现两次。另一方面,字符串“helno”是平衡的:其中存在五个不同的字母,并且每个字母只出现一次。字符串“hello”和“helno”只有一个位置不同:第四个字符。其他解决方案也是可能的。
在第二个测试用例中,字符串“codefofced”是平衡的,因为其中仅存在字母“c”、“o”、“d”、“e”和“f”,并且每个字母都恰好出现两次。
在第三个测试用例中,字符串“eeeee”是平衡的,因为其中只存在字母“e”。
在第四个测试用例中,给定的字符串“appall”已经是平衡的。