Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Making Equal

By RamprosadG · Limits 1s, 512 MB

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

InputOutput
2
abac
abbde
2
aaaa
3
bbbbb

    Discussion

    Statistics


    90% Solution Ratio

    Shorojit1997Earliest, 2w ago

    YouKnowWhoFastest, 0.0s

    kaium.Lightest, 627 kB

    mdvirusShortest, 142B

    Submit

    Login to submit