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 java.util.*;
import java.lang.*;
import java.io.*;

public class AEdu116 {
    public static void main(String[] args) throws java.lang.Exception {
        // your code goes here
        try {
            // Scanner sc=new Scanner(System.in);
            FastReader sc = new FastReader();
            int t = sc.nextInt();
            while (t-- > 0) {
                char[] arr=sc.next().toCharArray();
                int n=arr.length;
                if(arr[0]!=arr[n-1]){
                    int f=0;
                    int b=0;
                    int abc=0;
                    int bac=0;
                    for(int i=0;i<n-1;i++){
                        if(arr[i]=='a'&& arr[i+1]=='b')abc++;
                        if(arr[i]=='b' && arr[i+1]=='a')bac++;
                    }
                    
                    for(int i=0;i<n;i++){
                        if(i<n-1 && arr[i]!=arr[i+1]){
                            f=i+1;
                            break;
                        }
                    }
                    int bi=0;
                    for(int i=n-1;i>=0;i--){
                        if(i>0 && arr[i]!=arr[i-1]){
                            b=n-i;
                            bi=i;
                            break;
                        }
                    }
                    boolean done =false;
                    if(abc>bac){
                        if(!done && arr[0]==arr[1] && arr[0]=='a'){
                            arr[0]='b';
                            done=true;
                        }
                        if(!done && arr[n-1]==arr[n-2] && arr[n-1]=='b'){
                            arr[n-1]='a';
                            done =true;
                        }
                    }
                    if(bac>abc){
                        if(!done && arr[0]==arr[1] && arr[0]=='b'){
                            arr[0]='a';
                            done=true;
                        }
                        if(!done && arr[n-1]==arr[n-2] && arr[n-1]=='a'){
                            arr[n-1]='b';
                            done =true;
                        }

                    }
                    if(!done && f<b){
                        for(int i=0;i<f;i++){
                            if(arr[i]=='a')arr[i]='b';
                            else arr[i]='a';
                        }
                    }
                    else if(!done){
                        for(int i=n-1;i>=bi;i--){
                            if(arr[i]=='a')arr[i]='b';
                            else arr[i]='a';
                        }
                    }
                }
                
                for(char ch:arr)System.out.print(ch);
                System.out.println();
               //int n=sc.nextInt();
                /*int[] arr=new int[n];
                for(int i=0;i<n;i++){
                    arr[i]=sc.nextInt();
                }*/
                 /*long[] arr=new long[n];
                for(int i=0;i<n;i++){
                    arr[i]=sc.nextLong();
                }*/
            }
        } catch (Exception e) {
            return;
        }

    }
    public static int lowerbound(long[] ar,int k)
{
    int s=0;
    int e=ar.length;
    while (s !=e)
    {
        int mid = s+e>>1;
        if (ar[mid] <k)
        {
            s=mid+1;
        }
        else
        {
            e=mid;
        }
    }
    if(s==ar.length)
    {
        return -1;
    }
    return s;
}

    public static class pair {
        int ff;
        int ss;

        pair(int ff, int ss) {
            this.ff = ff;
            this.ss = ss;
        }
    }

    static int BS(int[] arr, int l, int r, int element) {
        int low = l;
        int high = r;
        while (high - low > 1) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < element) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (arr[low] == element) {
            return low;
        } else if (arr[high] == element) {
            return high;
        }
        return -1;
    }

    static int lower_bound(int[] arr, int l, int r, int element) {
        int low = l;
        int high = r;
        while (high - low > 1) {
            int mid = low + (high - low) / 2;
            if (arr[mid] < element) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (arr[low] >= element) {
            return low;
        } else if (arr[high] >= element) {
            return high;
        }
        return -1;
    }

    static int upper_bound(int[] arr, int l, int r, int element) {
        int low = l;
        int high = r;
        while (high - low > 1) {
            int mid = low + (high - low) / 2;
            if (arr[mid] <= element) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        if (arr[low] > element) {
            return low;
        } else if (arr[high] > element) {
            return high;
        }
        return -1;
    }

    public static int upperbound(long[] arr, int k) {
        int s = 0;
        int e = arr.length;
        while (s != e) {
            int mid = s + e >> 1;
            if (arr[mid] <= k) {
                s = mid + 1;
            } else {
                e = mid;
            }
        }
        if (s == arr.length) {
            return -1;
        }
        return s;
    }
    public static long pow(long x,long y,long mod){
        if(x==0)return 0l;
        if(y==0)return 1l;
        //(x^y)%mod
        if(y%2l==1l){
            return ((x%mod)*(pow(x,y-1l,mod)%mod))%mod;
        }
        return pow(((x%mod)*(x%mod))%mod,y/2l,mod);
    }

    public static long gcd_long(long a, long b) {
        // a/b,a-> dividant b-> divisor
        if (b == 0)
            return a;
        return gcd_long(b, a % b);
    }

    public static int gcd_int(int a, int b) {
        // a/b,a-> dividant b-> divisor
        if (b == 0)
            return a;
        return gcd_int(b, a % b);
    }

    public static int lcm(int a, int b) {
        int gcd = gcd_int(a, b);
        return (a * b) / gcd;
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return s;
        }

        Long nextLong() {
            return Long.parseLong(next());
        }
    }
}

/*
 * public static boolean lie(int n,int m,int k){ if(n==1 && m==1 && k==0){
 * return true; } if(n<1 || m<1 || k<0){ return false; } boolean
 * tc=lie(n-1,m,k-m); boolean lc=lie(n,m-1,k-n); if(tc || lc){ return true; }
 * return false; }
 */
