Non-Adjacent String Transformation

You are given a string consisting of lowercase English letters. Your task is to transform it so that no two adjacent characters are the same.

You can perform an operation on any character by changing it to one of the characters from the set \(\{a, b, c\}\). The goal is to achieve the transformation using the minimum possible number of operations. If there are multiple valid transformations, output any one.

Example: For the string "aa", one optimal transformation is "ab" which requires only 1 operation.

inputFormat

The input is read from stdin. The first line contains an integer (T) denoting the number of test cases. Each of the following (T) lines contains a non-empty string composed of lowercase English letters.

outputFormat

For each test case, output two lines to stdout:

• The first line should display the minimum number of operations required.
• The second line should display the resulting string after transformation.

## sample

2
ab
aa

0
ab
1
ab

</p>