Making Equal

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.

Input

The first line contains an integer $T$ ($1 \le T \le 100$), number of test cases. Each test case will contain a string $S$ ($1 \le \lvert S \rvert \le 10000$).

Output

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.

Sample

Input	Output
2 abac abbde	2 aaaa 3 bbbbb