CF1606A.AB Balance

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.

给你一个长度为 $n$ 的字符串 $s$，它仅由字符 a 和/或 b 组成。

令 $\operatorname{AB}(s)$ 表示子串 ab 在 $s$ 中出现的次数；类似地，$\operatorname{BA}(s)$ 表示子串 ba 在 $s$ 中出现的次数。

在一步操作中，你可以任选一个下标 $i$，并将 $s_i$ 替换为字符 a 或 b。

你需要执行的最少操作步数是多少，才能使得 $\operatorname{AB}(s) = \operatorname{BA}(s)$？

提示：

字符串 $d$ 在 $s$ 中作为子串出现的次数，定义为满足以下条件的下标 $i$ 的个数（其中 $1 \le i \le |s| - |d| + 1$）：子串 $s_i s_{i + 1} \dots s_{i + |d| - 1}$ 恰好等于 $d$。例如，$\operatorname{AB}($aabbbabaa$) = 2$，因为在该字符串中有两个下标 $i$ 满足条件：$i = 2$（对应子串 aabbbabaa）和 $i = 6$（对应子串 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.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 1000$）。随后是测试用例的描述。

每个测试用例仅有一行，包含一个字符串 $s$（$1 \le |s| \le 100$，其中 $|s|$ 表示字符串 $s$ 的长度），且 $s$ 仅由字符 a 和/或 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.

对于每个测试用例，输出经过最少步数操作后得到的字符串 $s$，使得 $\operatorname{AB}(s) = \operatorname{BA}(s)$。

如果存在多个满足条件的答案，输出任意一个即可。

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$.

在第一个测试用例中，$\operatorname{AB}(s) = 0$ 且 $\operatorname{BA}(s) = 0$（字符串 b 中不包含子串 ab 或 ba），因此可以保持 $s$ 不变。

在第二个测试用例中，$\operatorname{AB}(s) = 2$ 且 $\operatorname{BA}(s) = 2$，因此可以保持 $s$ 不变。

在第三个测试用例中，$\operatorname{AB}(s) = 1$ 且 $\operatorname{BA}(s) = 0$。例如，我们可以将 $s_1$ 改为 b，从而使两个值均变为 0。

在第四个测试用例中，$\operatorname{AB}(s) = 2$ 且 $\operatorname{BA}(s) = 1$。例如，我们可以将 $s_6$ 改为 a，从而使两个值均等于 $1$。