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 ≤ i ≤ |s| - |d| + 1) such that substring s_i s_{i + 1} ... 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.

Input

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

The first and only line of each test case contains a single string s (1 ≤ |s| ≤ 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 \operatorname{AB}(s) = \operatorname{BA}(s) you'll get making the minimum number of steps.

If there are multiple answers, print any of them.

Example

Input


4
b
aabbbabaa
abbb
abbaab


Output


b
aabbbabaa
bbbb
abbaaa

Note

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.
1
abbabababbabababbababbbabbbbabbbabaabaabba
 4
b
aabbbabaa
abbb
abbaab
 1
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbab

abbabababbabababbababbbabbbbabbbabaabaabba
 b
aabbbabaa
bbbb
bbbaab
 baaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbab

import enum
import random
import collections
import string
import math
import copy
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)


def input(): return sys.stdin.readline().rstrip("\r\n")


# mo = 998244353
mo = int(1e9+7)


def exgcd(a, b):
    if not b:
        return 1, 0
    y, x = exgcd(b, a % b)
    y -= a//b * x
    return x, y


def getinv(a, m):
    x, y = exgcd(a, m)
    return -1 if x == 1 else x % m


def comb(n, b):
    res = 1
    b = min(b, n-b)
    for i in range(b):
        res = res*(n-i)/(i+1)
        # res %= mo
    return res


def quickpower(a, n):
    res = 1
    while n:
        if n & 1:
            res = res * a % mo
        n >>= 1
        a = a*a % mo
    return res


def dis(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])


def getpref(x):
    if x > 1:
        return (x)*(x-1) >> 1
    else:
        return 0


def orafli(upp):
    primes = []
    marked = [False for i in range(upp+3)]
    prvs = [i for i in range(upp+3)]
    for i in range(2, upp):
        if not marked[i]:
            primes.append(i)
        for j in primes:
            if i*j >= upp:
                break
            marked[i*j] = True
            prvs[i*j] = j
            if i % j == 0:
                break
    return primes, prvs


def lower_ord(c: str) -> int:
    return ord(c)-97


def upper_ord(c: str) -> int:
    return ord(c) - 65


def read_list():
    return [int(i) for i in input().split()]


def read_int():
    s = input().split()
    if len(s) == 1:
        return int(s[0])
    else:
        return map(int, s)


def ask(s, i, j):
    print(f"{s} {i} {j}", flush=True)


def answer(x):
    print(f"finish {x}", flush=True)

import functools

# primes, prvs = orafli(100010)

import itertools
from fractions import Fraction

import random
# A = list(map(list,(zip(*A))))


def lowbit(x):
    return -x&x

def pref(x):
    return x*(x+1)>>1

def cum(sx, mx):
    """???"""
    return (sx+mx)*(mx-sx+1)>>1



def solve():
    s = input()
    if len(s)==1:
        print(s)
    elif len(s)==2:
        if s[0]!=s[1]:
            print('aa')
        else:
            print(s)
    elif len(s)==3:
        if s[0]!=s[1]!=s[2]:
            print(s)
        else:
            if s.count('a')>s.count('b'):
                print('aaa')
            else:
                print('bbb')
    else:
        def cntt(s):
            ab = 0
            ba = 0
            for p, i in enumerate(s[1:]):
                if s[p] == 'a' and i=='b':
                    ab+=1
                elif s[p]=='b' and i=='a':
                    ba+=1
            return ab, ba
        ab,ba = cntt(s)
        if ab==ba:
            print(s)
        else:
            if ab>ba:
                if s[:2]=='aa':
                    print('b'+s[1:])
                    return
                if s[:2]=='ab':
                    print('bb'+s[2:])
                    return
                if s[-2:]=='bb':
                    print(s[:-1]+'a')
                    return
                if s[-2:]=='ab':
                    print(s[:-2]+'aa')
                    return
                raise NameError
            else:
                if s[:2]=='bb':
                    print('a'+s[1:])
                    return
                if s[:2]=='ba':
                    print('aa'+s[2:])
                    return
                if s[-2:]=='aa':
                    print(s[:-1]+'b')
                    return
                if s[-2:]=='ba':
                    print(s[:-2]+'bb')
                    return






    # n = read_int()

    


            


    
# fi = open('C:\\cppHeaders\\CF2020.12.17\\test.data', 'r')
# def input(): return fi.readline().rstrip("\r\n")
# primes, prv = orafli(10001)
# solve()
T = int(input())
# T = 1



for ti in range(T):
    solve()
    # except:
        # traceback.print_exc()


"""
1
3 5 1
*...*
.***.
.**..
"""