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

public class TaskA {
    public static char reverse(char a){
        if(a=='a') return 'b';
        else return 'a';
    }
    public static String getString(String s){
        StringBuilder ans = new StringBuilder();
        ans.append(s);
        ans.setCharAt(0,reverse(s.charAt(0)));
        return ans.toString();
    }
    public static int count(String s,String t){
        int cnt = 0;
        for(int i=0;i<s.length()-1;i++){
            if(s.charAt(i)==t.charAt(0)&&s.charAt(i+1)==t.charAt(1)) cnt++;
        }
        return cnt;
    }
    public static void solve(FastReader in,PrintWriter out,int nTestCase) {
        String a = in.next();
        int abCnt = count(a,"ab");
        int baCnt = count(a,"ba");
        if(abCnt==baCnt){
            out.println(a);
            return;
        }
        String ans = "";
        ans = getString(a);
        out.println(ans);
    }
    public static void main(String[] args) {
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        int T = 1;
        T = in.nextInt();
        for(int tt=1;tt<=T;tt++) {
            solve(in,out,tt);
        }
        out.close();
    }
    static final Random random=new Random();
    static void fastSort(int[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
            int temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
    static void fastSort(char[] a) {
        int n=a.length;//shuffle, then sort
        for (int i=0; i<n; i++) {
            int oi=random.nextInt(n);
            char temp=a[oi];
            a[oi]=a[i]; a[i]=temp;
        }
        Arrays.sort(a);
    }
    static int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }
    static class Pair implements Comparable<Pair>{
        int  a;
        int  b;
        public Pair(int  a, int  b) {
            this.a = a;
            this.b = b;
        }
        public int compareTo(Pair o) {
            if(this.a==o.a)
                return (int)(this.b - o.b);
            return (int)(this.a - o.a);
        }
    }
    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());
        }

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

        public int[] readArray(int n) {
            int[] a=new int[n];
            for (int i=0; i<n; i++) a[i]=nextInt();
            return a;
        }
    }
}

