#include<bits/stdc++.h>
 
using namespace std;
 
void solve()
{
	string s;
	cin >> s;
	int n = s.size();
	int idx = -1;
	for(int i = 0; i + 1 < n; i++)
		if(s[i] == s[i + 1])
			idx = i;
	if(idx == -1)
	{
		if(s.back() == 'a') cout << (s + "b") << endl;
		else cout << (s + "a") << endl;
	}
	else
	{
		string t = "a";
		if(s[idx] == 'a') t = "b";
		cout << s.substr(0, idx + 1) + t + s.substr(idx + 1) << endl;
	}
}
 
int main()
{
	int t;
	cin >> t;
	for(int i = 0; i < t; i++)
		solve();
}

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<string> s(2);
    for (auto& x : s) cin >> x;
    int ans = 0;
    for (int i = 1; i < n - 1; ++i) {
      bool ok = true;
      ok &= (s[0][i] == '.' && s[1][i] == '.');
      ok &= (s[0][i - 1] != s[1][i - 1]);
      ok &= (s[0][i + 1] != s[1][i + 1]);
      ok &= (s[0][i - 1] == s[0][i + 1]);
      ans += ok;
    }
    cout << ans << '\n';
  }
}

import java.util.LinkedList
 
fun main() {
    repeat(readln().toInt()) {
        val n = readln().toInt()
        val s = readln()
 
        var ans = 0L
        val bracketPositions = LinkedList<Int>()
        for (i in s.indices) {
            var c = s[i]
            if (c == '_') {
                c = if (bracketPositions.isEmpty()) '(' else ')'
            }
            if (c == ')') {
                ans += i - bracketPositions.pollLast()
            }
            else
                bracketPositions.addLast(i)
        }
        println(ans)
    }
}

#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1e9;
 
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> p;
        g[p - 1].push_back(i);
    }
    
    auto check = [&](auto&& self, int v, int x) -> bool {
      if (x > INF) return false;
      bool isLeaf = true;
      if (v) x += max(0, x - a[v]);
      for (auto u : g[v]) {
        isLeaf = false;
        if (!self(self, u, x)) return false;
      }
      return (!isLeaf || x <= a[v]);
    };
    
    int l = 1, r = INF;
    while (l <= r) {
      int mid = (l + r) / 2;
      if (check(check, 0, mid)) {
        l = mid + 1;
      } else {
        r = mid - 1;
      }
    }
    
    cout << a[0] + l - 1 << '\n';
  }
}

#include <bits/stdc++.h>
#include "ext/pb_ds/assoc_container.hpp"
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
struct query{
	int i, j;
};
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	forn(i, n) cin >> a[i];
	vector<vector<query>> q(n + 1);
	forn(j, m){
		int i, x;
		cin >> i >> x;
		--i;
		q[x].push_back({i, j});
	}
	forn(i, n + 1){
		sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){
			return a.i > b.i;
		});
	}
	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int i, int j){
		return a[i] > a[j];
	});
	
	vector<int> cur(n + 1);
	vector<char> ans(m);
	ordered_set<int> alive(ord.begin(), ord.end());
	for (int lvl = 1; lvl <= n; ++lvl){
		for (int k = 1; k <= n; ++k){
			if (cur[k] >= n) break;
			int x = alive.order_of_key(cur[k]);
			int nxt = x + k - 1 >= int(alive.size()) ? n : *alive.find_by_order(x + k - 1);
			while (!q[k].empty() && q[k].back().i <= nxt){
				ans[q[k].back().j] = (a[q[k].back().i] >= lvl);
				q[k].pop_back();
			}
			cur[k] = nxt + 1;
		}
		while (!ord.empty() && a[ord.back()] == lvl){
			alive.erase(ord.back());
			ord.pop_back();
		}
	}
	
	for (auto x : ans) cout << (x ? "YES" : "NO") << '\n';
	return 0;
}

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); i++)
 
using namespace std;
 
struct query{
	int i, j;
};
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	forn(i, n) cin >> a[i];
	vector<vector<query>> q(n + 1);
	forn(j, m){
		int i, x;
		cin >> i >> x;
		--i;
		q[x].push_back({i, j});
	}
	forn(i, n + 1) sort(q[i].begin(), q[i].end(), [](const query &a, const query &b){
		return a.i > b.i;
	});
	
	int P = min(1000, n + 1);
	
	vector<char> ans(m);
	for (int k = 1; k < P; ++k){
		int cur = 1;
		int cnt = 0;
		forn(i, n){
			bool fl = false;
			if (a[i] >= cur){
				++cnt;
				fl = true;
				if (cnt == k){
					++cur;
					cnt = 0;
				}
			}
			while (!q[k].empty() && q[k].back().i == i){
				ans[q[k].back().j] = fl;
				q[k].pop_back();
			}
		}
	}
	
	vector<int> sum1(n), sum2(n);
	int p2 = ceil(sqrt(n + 2));
	
	auto add = [&](int i){
		int bl = i / p2;
		for (int j = bl + 1; j * p2 < n; ++j)
			++sum1[j];
		for (int j = i; j < (bl + 1) * p2 && j < n; ++j)
			++sum2[j];
	};
	
	int mx = n / P + 5;
	vector<vector<int>> pos(mx);
	forn(i, n){
		if (a[i] < mx)
			pos[a[i]].push_back(i);
		else
			add(i);
	}
	for (auto &it : pos) reverse(it.begin(), it.end());
	
	for (int k = P; k <= n; ++k){
		while (true){
			int mn = n;
			int who = -1;
			forn(lvl, mx) if (!pos[lvl].empty()){
				int i = pos[lvl].back();
				if (mn < i) continue;
				int cnt = sum1[i / p2] + sum2[i];
				if (a[i] >= cnt / k + 1){
					mn = i;
					who = lvl;
				}
			}
			if (who == -1) break;
			add(mn);
			pos[who].pop_back();
		}
		for (auto it : q[k]){
			int lvl = a[it.i];
			ans[it.j] = (lvl >= mx || pos[lvl].empty() || pos[lvl].back() > it.i);
		}
	}
	
	for (auto x : ans) cout << (x ? "YES" : "NO") << '\n';
	return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
const int MOD = 998244353;
 
int add(int x, int y)
{
 	x += y;
 	while(x >= MOD) x -= MOD;
 	while(x < 0) x += MOD;
 	return x;
}
 
int mul(int x, int y)
{
 	return (x * 1ll * y) % MOD;
}
 
int main()
{
 	int n, x, m;
 	cin >> n >> x >> m;
 	vector<int> fib = {0, 1};
 	for(int i = 2; i <= 30; i++)
 		fib.push_back(fib[i - 1] + fib[i - 2]);
 
 
 	int max_sum = fib[x] * n;
 	vector<vector<int>> dp(max_sum + 1, vector<int>(n + 1));
 	dp[0][0] = 1;
 	for(int i = 1; i <= x; i++)
 		for(int j = 0; j < max_sum; j++)
 			for(int k = 0; k < n; k++)
 			{
 			 	if(j + fib[i] <= max_sum)
 			 		dp[j + fib[i]][k + 1] = add(dp[j + fib[i]][k + 1], dp[j][k]);
 			}
	
	vector<int> cost(max_sum + 1, 1e9);
	cost[0] = 0;
	for(int j = 1; j <= max_sum; j++)
		for(int i = 1; i <= 30; i++)
			if(j >= fib[i])
				cost[j] = min(cost[j], cost[j - fib[i]] + 1);
 
	int ans = 0;
	for(int i = 0; i <= max_sum; i++)
		if(cost[i] == m)
			ans = add(ans, dp[i][n]);
	cout << ans << endl;
}