There is a digit string of length . Define be the number of times digit appears in the string .

You can arbitrarily modify each character of into any digit so that the maximum value of is less than or equal to . Define as the modified string, then the cost of modification is . Minimize the cost and output a lexicographically smallest .

A digit string only contains characters from to .

输入描述:

This problem contains multiple test cases.
The first line contains an integer  indicating the number of test cases.
For each test case, the first line contains two integers  (). It's guaranteed that there always is a solution.
The second line contains a digit string  of length .
It's guaranteed that .

输出描述:

For each test case, output two lines.
The first line contains an integer, the minimum cost.
The second line is a digit string  of length , which is the lexicographically smallest solution.

2
6 2
122223
6 2
122333

2
112233
1
122334