A. AB Balance
strings
You are given a string \(s\) of length \(n\) consisting of characters a and/or b.Let \(\operatorname{AB}(s)\) be the number of occurrences of string ab in \(s\) as a substring. Analogically, \(\operatorname{BA}(s)\) is the number of occurrences of ba in \(s\) as a substring.In one step, you can choose any index \(i\) and replace \(s_i\) with character a or b.What is the minimum number of steps you need to make to achieve \(\operatorname{AB}(s) = \operatorname{BA}(s)\)?Reminder:The number of occurrences of string \(d\) in \(s\) as substring is the number of indices \(i\) (\(1 \le i \le |s| - |d| + 1\)) such that substring \(s_i s_{i + 1} \dots s_{i + |d| - 1}\) is equal to \(d\). For example, \(\operatorname{AB}(\)aabbbabaa\() = 2\) since there are two indices \(i\): \(i = 2\) where aabbbabaa and \(i = 6\) where aabbbabaa.
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 1000\)). Description of the test cases follows.The first and only line of each test case contains a single string \(s\) (\(1 \le |s| \le 100\), where \(|s|\) is the length of the string \(s\)), consisting only of characters a and/or b.
For each test case, print the resulting string \(s\) with \(\operatorname{AB}(s) = \operatorname{BA}(s)\) you'll get making the minimum number of steps.If there are multiple answers, print any of them.
In the first test case, both \(\operatorname{AB}(s) = 0\) and \(\operatorname{BA}(s) = 0\) (there are no occurrences of ab (ba) in b), so can leave \(s\) untouched.In the second test case, \(\operatorname{AB}(s) = 2\) and \(\operatorname{BA}(s) = 2\), so you can leave \(s\) untouched. In the third test case, \(\operatorname{AB}(s) = 1\) and \(\operatorname{BA}(s) = 0\). For example, we can change \(s_1\) to b and make both values zero.In the fourth test case, \(\operatorname{AB}(s) = 2\) and \(\operatorname{BA}(s) = 1\). For example, we can change \(s_6\) to a and make both values equal to \(1\).