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.Arrays;
import java.util.StringTokenizer;


//start of Scanner class


public class msa {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter pw = new PrintWriter(System.out);
    static StringTokenizer st;
    static Snner sc = new Snner(System.in);

    static public int maximumProduct(int[] num) {

        int max1 = 1, max2 = 1;
        Arrays.sort(num);
        for (int i = 0; i < 3; i++) {
            max1 *= num[num.length - 1 - i];
            if (i < 2)
                max2 *= num[i];
        }
        max2 *= num[num.length - 1];
        return max1 > max2 ? max1 : max2;
    }

    public static void main(String args[]) throws NumberFormatException, IOException {
        long t = sc.nextLong();

        while (t-- > 0) {
            pw.println(solve_a(sc.nextLine()));
            /*            int caves = sc.nextInt();
            int arr[][] = new int[caves][];

            while (caves-- > 0) {
                int mon = sc.nextInt();
                int ca = arr.length - caves - 1;
                arr[ca] = new int[mon];
                for (int i = 0; i < mon; i++) arr[ca][i] = sc.nextInt();

            }
            pw.println(b(arr));
        }*/
        }
        pw.close();

    }

    //segtree
    static long b(int arr[][]) {
        int s = 1;
        int e = (int) 10e9;
        int mid;
        while (s <= e) {
            mid = s + ((e - s) >> 1);
            int temp = sum(arr, mid);
            if (temp < 0) s = mid + 1;
            else if (temp == 0) return mid;
            else e = mid - 1;

        }
        return s;
    }

    static long solve(long arr[][]) {
        long b[] = new long[arr.length];
        long max0 = Long.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            long max = Long.MIN_VALUE;
            for (int j = 1; j < arr[i].length; j++) {
                max = Math.max(max, arr[i][j] - j + 1);
            }
            long k = arr[i].length;
            b[i] = max - k;
        }
        Arrays.sort(b);
        return b[b.length - 1];
    }

    private static int sum(int[][] arr, int mid) {
        int sum = arr[0][0] + 1;

        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr[i].length; j++) {
                if (sum < arr[i][j]) sum += 1 + arr[i][j] - sum;
                sum++;
            }
        }
        return mid - sum;

    }

    static long solveb(long n, long k) {


        long done = 1;
        long poss = 1;
        long i = 0;
        if (k == 1) return n - 1;
        if (k > n) k = n;
        while (done < k) {
            i++;
            done += poss;
            poss = done;
        }
        i += Math.ceil(((double) n - (double) done) / (double) k);
        return i;
    }

    //
    //end of public clas
    static String solve_a(String x) {
        int a = 0, b = 0;
        for (int i = 0; i < x.length() - 1; i++) {
            if (x.charAt(i) != x.charAt(i + 1)) {
                if (x.charAt(i) == 'a') a++;
                else b++;
            }
        }
        //char aa[] = x.toCharArray();
        StringBuilder xx = new StringBuilder(x);
        if (a == b) return x;

        else if (a > b) {
            for (int i = 0; i < x.length(); i++) {
                if (x.charAt(i) == 'a') {
                    xx.setCharAt(i, 'b');
                    break;
                }
            }
        } else {
            for (int i = 0; i < x.length(); i++) {
                if (x.charAt(i) == 'b') {
                    xx.setCharAt(i, 'a');
                    break;
                }

            }
        }
        return xx.toString();
    }

    int count(String x) {
        int c = 0;
        for (int i = 0; i < x.length() - 1; i++) {
            if (x.charAt(i) != x.charAt(i + 1))
                c++;
        }
        return c;
    }



    boolean prime_or_not(long x) {
        if (x % 2 == 0 || x % 3 == 0) return false;
        for (long i = 6; i * i < x; i += 6)
            if (x % (i + 1) == 0 || x % (i - 1) == 0) return false;

        return true;
    }

    static class Snner {
        StringTokenizer st;
        BufferedReader br;

        public Snner(InputStream s) {
            br = new BufferedReader(new InputStreamReader(s));
        }

        public Snner(FileReader r) {
            br = new BufferedReader(r);
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

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

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

        public String nextLine() throws IOException {
            return br.readLine();
        }

        public double nextDouble() throws IOException {
            String x = next();
            StringBuilder sb = new StringBuilder("0");
            double res = 0, f = 1;
            boolean dec = false, neg = false;
            int start = 0;
            if (x.charAt(0) == '-') {
                neg = true;
                start++;
            }
            for (int i = start; i < x.length(); i++)
                if (x.charAt(i) == '.') {
                    res = Long.parseLong(sb.toString());
                    sb = new StringBuilder("0");
                    dec = true;
                } else {
                    sb.append(x.charAt(i));
                    if (dec)
                        f *= 10;
                }
            res += Long.parseLong(sb.toString()) / f;
            return res * (neg ? -1 : 1);
        }

        public long[] nextlongArray(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

        public Long[] nextLongArray(int n) throws IOException {
            Long[] a = new Long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

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

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

        public boolean ready() throws IOException {
            return br.ready();
        }

    }

    class SegmentTree {
        int N, n;
        long[] arr, a;
        long ident;

        //arr = segment tree;
        //a is input_array but (1 based , its len is completed to power 2 with identity values if possible );
        //N =len of a;
        //n=num of input array element ;
        // All index are 1 based except for am array (in the constructor);

        SegmentTree(long[] am, long ident) {
            n = am.length;
            N = 1;
            while (N < n) N *= 2;

            a = new long[N + 1];
            this.ident = ident;
            Arrays.fill(a, ident);
            for (int i = 0; i < n; i++) a[i + 1] = am[i];

            arr = new long[2 * N];
            Arrays.fill(arr, ident);

            build(1, 1, N);
        }

        long build(int node, int l, int r) {
            if (l == r) return arr[node] = a[node - (N - 1)];
            int mid = (l + r) / 2;
            return arr[node] = build(2 * node, l, mid) + build(2 * node + 1, mid + 1, r);

        }

        void update_point(int index, long new_value) {
            arr[N - 1 + index] = new_value;
            index = index + N - 1;
            while (index > 1) {
                index /= 2;
                arr[index] = arr[2 * index] + arr[2 * index + 1];
            }
        }

        long query(int l, int r) {
            return q(1, 1, N, l, r);

        }

        private long q(int node, int s, int e, int l, int r) {
            if (l > e || r < s) return ident;
            if (s >= l && e <= r) return arr[node];
            int mid = (s + e) / 2;
            return q(node * 2, s, mid, l, r) + q(node * 2 + 1, mid + 1, e, l, r);
        }

    }

}