CF1781C.Equal Frequencies

Let's call a string balanced if all characters that are present in it appear the same number of times. For example, "coder", "appall", and "ttttttt" are balanced, while "wowwow" and "codeforces" are not.

You are given a string $s$ of length $n$ consisting of lowercase English letters. Find a balanced string $t$ of the same length $n$ consisting of lowercase English letters that is different from the string $s$ in as few positions as possible. In other words, the number of indices $i$ such that $s_i \ne t_i$ should be as small as possible.

我们称一个字符串是平衡的，当且仅当其中所有出现的字符的出现次数均相同。例如，“coder”、“appall”和“ttttttt”是平衡的，而“wowwow”和“codeforces”则不是。

给定一个长度为 $n$ 的字符串 $s$，它仅由小写英文字母组成。请找出一个长度同样为 $n$、也仅由小写英文字母组成的平衡字符串 $t$，使得 $t$ 与 $s$ 在尽可能少的位置上不同。换言之，使得满足 $s_i \ne t_i$ 的下标 $i$ 的个数最小。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

Each test case consists of two lines. The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the string $s$.

The second line contains the string $s$ of length $n$ consisting of lowercase English letters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例由两行组成。第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

For each test case, print the smallest number of positions where string $s$ and a balanced string $t$ can differ, followed by such a string $t$.

If there are multiple solutions, print any. It can be shown that at least one balanced string always exists.

对于每个测试用例，输出字符串 $s$ 与一个平衡字符串 $t$ 之间可能的最小差异位置数，并随后输出这样一个字符串 $t$。

若存在多个解，输出任意一个即可。可以证明，至少存在一个平衡字符串。

In the first test case, the given string "hello" is not balanced: letters 'h', 'e', and 'o' appear in it once, while letter 'l' appears twice. On the other hand, string "helno" is balanced: five distinct letters are present in it, and each of them appears exactly once. Strings "hello" and "helno" differ in just one position: the fourth character. Other solutions are possible too.

In the second test case, string "codefofced" is balanced since only letters 'c', 'o', 'd', 'e', and 'f' are present in it, and each of them appears exactly twice.

In the third test case, string "eeeee" is balanced since only letter 'e' is present in it.

In the fourth test case, the given string "appall" is already balanced.

在第一个测试用例中，给定字符串 "hello" 不是平衡的：其中字母 'h'、'e' 和 'o' 各出现一次，而字母 'l' 出现了两次。另一方面，字符串 "helno" 是平衡的：它包含恰好五个互不相同的字母，且每个字母均恰好出现一次。字符串 "hello" 和 "helno" 仅在第四个位置上不同。其他可行解也存在。

在第二个测试用例中，字符串 "codefofced" 是平衡的，因为其中仅包含字母 'c'、'o'、'd'、'e' 和 'f'，且每个字母均恰好出现两次。

在第三个测试用例中，字符串 "eeeee" 是平衡的，因为其中仅包含字母 'e'。

在第四个测试用例中，给定字符串 "appall" 已经是平衡的。