You are given a string S, that contains only lowercase English letters. You can change a letter to another letter. You have to make the all letters same. What is the minimum number of changes needed to make all letters same and what is the changed string?
If there are multiple string determine the lexicographically smallest one.
The first line contains an integer
$1 \le T \le 100$), number of test cases. Each test case will contain a string
$1 \le \lvert S \rvert \le 10000$).
For each test case print two lines:
The first line will contain the minimum number changes needed. The second line will contain the changed string.
2 abac abbde
2 aaaa 3 bbbbb