给我们一个长度为n，仅有字符‘a’，‘b’构成的字符串s, 定义：AB(s)为该字符串中子串为”ab”的子串个数，BA(s)为该字符串中子串为”ba”的子串个数。比如：s=”ababbbab”, 则AB(s)=3, BA(s)=2。如果一个字符串s满足：AB(s)=BA(s),则称该字符串为平衡字符串。

在一次操作中，我们可以任选一个整数i(1<=i<=n), 将si替换为字符‘a’或’b’。问最少经过几次操作后，该字符串s会转换为平衡字符串？

第一行只有一个整数t(1≤t≤1000)：测试用例的数量。

接下来共t行，每个测试用例一行一个字符串；

共t行，每个测试用例一行一个字符串：经过最少操作次数之后所得到的平衡字符串；

如果有多个结果字符串，任意输出一个即可。

在第一个测试用例中，AB(s)=BA(s)=0, 不需要操作；“b”即为结果字符串；

在第二个测试用例中，AB(s)=BA(s)=2, 不需要操作；“aabbbabaa“即为结果字符串；

在第三个测试用例中，AB(s)=1，BA(s)=0，一种操作方法是将s1改为‘b’，从而使得AB(s)=0，此时结果字符串为：”bbbb“;

在第四个测试用例中，AB(s)=2，BA(s)=1，一种操作方法是将s6改为‘a’，从而使得AB(s)=1，此时结果字符串为：” abbaaa“;