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

    public class Main {

        // -- static variables --- //
        static FastReader sc = new FastReader();
        static PrintWriter out = new PrintWriter(System.out);
        static int mod = (int) 1000000007;
        public static void main(String[] args) throws Exception {
         
            int t=sc.nextInt();
            while(t-->0)
            Main.go();
            // out.println();
            out.flush();
        }

        // >>>>>>>>>>>>>>>>>>> Code Starts <<<<<<<<<<<<<<<<<<<< //
        static class pair{
            int x,y;
            pair(int x,int y){
                this.x=x;
                this.y=y;
            }
        }

        static void go() throws Exception {
        	char a[]=sc.next().toCharArray();
        	int n=a.length;
        	int ab=0;
        	int ba=0;
        	for(int i=0;i<n-1;i++) {
        		if(a[i]=='a' && a[i+1]=='b') {
        			ab+=1;
        		}
        	}
         	for(int i=n-1;i>0;i--) {
        		if(a[i]=='a' && a[i-1]=='b') {
        			ab--;
        		}
        	}
         	if(ab==0) {
         		out.println(String.valueOf(a));
         		return;
         	}
         	if(ab>0) {
           	for(int i=0;i<n-1;i++) {
          		if(a[i]=='a' && a[i+1]=='b'&& ab>0) {
          			int j=i;
          			while(j>=0&&a[j]=='a') {
          				j--;
          			}
          			a[j+1]='b';
          			ab--;
          		}
          	}
           	out.println(String.valueOf(a));
         	}else {
          	for(int i=n-1;i>0;i--) {
          		if(a[i]=='a' && a[i-1]=='b' && ab<0) {
          			int j=i;
          			while(j<n&&a[j]=='a') {
          				j++;
          			}
          			a[j-1]='b';
          			ab++;;
          		}
          	}
           	out.println(String.valueOf(a));
         	}
        	
        	
	        	
        	
        }
        	
    
        


    
        // >>>>>>>>>>> Code Ends <<<<<<<<< //

        // --For Rounding--//
        static double round(double value, int places) {

            if (places < 0)
                throw new IllegalArgumentException();
            BigDecimal bd = new BigDecimal(Double.toString(value));
            bd = bd.setScale(places, RoundingMode.HALF_UP);
            return bd.doubleValue();
        }

        // ----Greatest Common Divisor-----//
        static long gcd(long a, long b) {
            if (b == 0) {
                return a;
            }
            return gcd(b, a % b);
        }

        // --- permutations and Combinations ---//
        static long fact[];
        static long invfact[];

        static long ncr(int n, int k) {
            if (k < 0 || k > n) {
                return 0;
            }
            long x = fact[n];
            long y = fact[k];
            long yy = fact[n - k];
            long ans = (x / y);
            ans = (ans / yy);
            return ans;
        }

        // ---sieve---//
        static int prime[] = new int[1000006];

        // static void sieve() {
        //     Arrays.fill(prime, 1);
        //     prime[0] = 0;
        //     prime[1] = 0;
        //     for (int i = 2; i * i <= 1000005; i++) {
        //         if (prime[i] == 1)
        //             for (int j = i * i; j <= 1000005; j += i) {
        //                 prime[j] = 0;
        //             }
        //     }
        // }

        // ---- Manual sort ------//
        static void sort(long[] a) {
            ArrayList<Long> aa = new ArrayList<>();
            for (long i : a) {
                aa.add(i);
            }
            Collections.sort(aa);
            for (int i = 0; i < a.length; i++)
                a[i] = aa.get(i);
        }

        static void sort(int[] a) {
            ArrayList<Integer> aa = new ArrayList<>();
            for (int i : a) {
                aa.add(i);
            }
            Collections.sort(aa);
            for (int i = 0; i < a.length; i++)
                a[i] = aa.get(i);
        }

        // --- Fast exponentiation ---//
        static long pow(long x, long y) {
            long res = 1l;
            while (y != 0) {
                if (y % 2 == 1) {
                    res = (x * res);
                }
                y /= 2;
                x = (x * x);
            }
            return res;
        }

        // >>>>>>>>>>>>>>> Fast IO <<<<<<<<<<<<<< //
        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());
            }

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

            double nextDouble() {
                return Double.parseDouble(next());
            }

            int[] intArray(int n) {
                int a[] = new int[n];
                for (int i = 0; i < n; i++)
                    a[i] = sc.nextInt();
                return a;
            }

            long[] longArray(int n) {
                long a[] = new long[n];
                for (int i = 0; i < n; i++)
                    a[i] = sc.nextLong();
                return a;
            }

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