## Algorithm

A. AB Balance
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a string s of length n consisting of characters a and/or b.

Let AB(s)AB⁡(�) be the number of occurrences of string ab in s as a substring. Analogically, BA(s)BA⁡(�) is the number of occurrences of ba in s as a substring.

In one step, you can choose any index i and replace si�� with character a or b.

What is the minimum number of steps you need to make to achieve AB(s)=BA(s)AB⁡(�)=BA⁡(�)?

Reminder:

The number of occurrences of string d in s as substring is the number of indices i (1i|s||d|+11≤�≤|�|−|�|+1) such that substring sisi+1si+|d|1����+1…��+|�|−1 is equal to d. For example, AB(AB⁡(aabbbabaa)=2)=2 since there are two indices ii=2�=2 where aabbbabaa and i=6�=6 where aabbbabaa.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1t10001≤�≤1000). Description of the test cases follows.

The first and only line of each test case contains a single string s (1|s|1001≤|�|≤100, where |s||�| is the length of the string s), consisting only of characters a and/or b.

Output

For each test case, print the resulting string s with AB(s)=BA(s)AB⁡(�)=BA⁡(�) you'll get making the minimum number of steps.

If there are multiple answers, print any of them.

Example
input
Copy
4
b
aabbbabaa
abbb
abbaab

output
Copy
b
aabbbabaa
bbbb
abbaaa
Note

In the first test case, both AB(s)=0AB⁡(�)=0 and BA(s)=0BA⁡(�)=0 (there are no occurrences of ab (ba) in b), so can leave s untouched.

In the second test case, AB(s)=2AB⁡(�)=2 and BA(s)=2BA⁡(�)=2, so you can leave s untouched.

In the third test case, AB(s)=1AB⁡(�)=1 and BA(s)=0BA⁡(�)=0. For example, we can change s1�1 to b and make both values zero.

In the fourth test case, AB(s)=2AB⁡(�)=2 and BA(s)=1BA⁡(�)=1. For example, we can change s6�6 to a and make both values equal to 11.

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--){
string s;
cin>>s;
if(s[0] == s[s.length() - 1]){
cout<<s<<endl;
}
else{
s[0] = s[s.length() - 1];
cout<<s<<endl;
}
}

}
Copy The Code &

Input

cmd
4
b
aabbbabaa
abbb
abbaab

Output

cmd
b
aabbbabaa
bbbb
abbaaa