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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.io.*;
import java.util.*;
import java.text.DecimalFormat;
import java.math.*;
 
public class Main {
 
static int  mod = 1000000007;
/*****************code By Priyanshu *******************************************/ 
 
    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;
        }
    }
    // this > other return +ve
    // this < other return -ve
    // this == other return 0
     public static class Pair implements Comparable<Pair> {
      long st;
      long et;
 
      public Pair(long st, long et) {
         this.st = st;
         this.et = et;
      }
 
      public int compareTo(Pair other) {
         if (this.st != other.st) {
            return (int)(this.st - other.st);
         } else {
            return (int)(this.et - other.et);
         }
      }
   }
 
    static long fastPower(long a, long b, int n) {
            
            long res = 1;
            
            while ( b > 0) {
                
                if ( (b&1) != 0) {
                    res = (res * a % n) % n;
                }
                
                a = (a % n * a % n) % n;
                b =  b >> 1;
            }
            
            return res;
            
        }
 
     // function to find
    // the rightmost set bit
    static int PositionRightmostSetbit(int n)
    {
        // Position variable initialize
        // with 1 m variable is used to
        // check the set bit
        int position = 1;
        int m = 1;
 
        while ((n & m) == 0) {
 
            // left shift
            m = m << 1;
            position++;
        }
        return position;
    }
    
         // used for swapping ith and jth elements of array
      // public static void swap(int[] arr, int i, int j) {
      //   int temp = arr[i];
      //   arr[i] = arr[j];
      //   arr[j] = temp;
      // }
        public static void swap(long i, long j) {
        long temp = i;
        i = j;
        j = temp;
      }
 
 
    static boolean palindrome(String s) {
        return new StringBuilder(s).reverse().toString().equals(s);
    }
    
  static boolean isPerfectSquare(double x)
    {
            double sr = Math.sqrt(x);
            return ((sr * sr) == x);     
    }
 
 
 public static long gcd(long a, long b)
    {
      if (b == 0)
        return a;
      return gcd(b, a % b);
    }
    
   
 
   static int nod(long l) {
       if(l>=1000000000000000000l) return 19;
       if(l>=100000000000000000l) return 18;
       if(l>=10000000000000000l) return 17;
       if(l>=1000000000000000l) return 16;
       if(l>=100000000000000l) return 15;
       if(l>=10000000000000l) return 14;
       if(l>=1000000000000l) return 13;
       if(l>=100000000000l) return 12;
       if(l>=10000000000l) return 11;
       if(l>=1000000000) return 10;
       if(l>=100000000) return 9;
       if(l>=10000000) return 8;
       if(l>=1000000) return 7;
       if(l>=100000) return 6;
       if(l>=10000) return 5;
       if(l>=1000) return 4;
       if(l>=100) return 3;
       if(l>=10) return 2;
       return 1;
    }
      //Arrays.sort(a,(c,d) -> Integer.compare(c[0],d[0]));
 
    
    public static boolean areAllBitsSet(int n )
    {
        // all bits are not set
        if (n == 0)
            return false;
     
        // if true, then all bits are set
        if (((n + 1) & n) == 0)
            return true;
     
        // else all bits are not set
        return false;
    }
 
     public static long[] sort(long[] arr) {
        List<Long> temp = new ArrayList();
        for (long i : arr) temp.add(i);
        Collections.sort(temp);
        int start = 0;
        for (long i : temp) arr[start++] = i;
        return arr;
    }
   
 
 
        public static int[] radixSort2(int[] a)
    {
        int n = a.length;
        int[] c0 = new int[0x101];
        int[] c1 = new int[0x101];
        int[] c2 = new int[0x101];
        int[] c3 = new int[0x101];
        for(int v : a) {
            c0[(v&0xff)+1]++;
            c1[(v>>>8&0xff)+1]++;
            c2[(v>>>16&0xff)+1]++;
            c3[(v>>>24^0x80)+1]++;
        }
        for(int i = 0;i < 0xff;i++) {
            c0[i+1] += c0[i];
            c1[i+1] += c1[i];
            c2[i+1] += c2[i];
            c3[i+1] += c3[i];
        }
        int[] t = new int[n];
        for(int v : a)t[c0[v&0xff]++] = v;
        for(int v : t)a[c1[v>>>8&0xff]++] = v;
        for(int v : a)t[c2[v>>>16&0xff]++] = v;
        for(int v : t)a[c3[v>>>24^0x80]++] = v;
        return a;
    } 
 
    public static void print( int arr[] ){
        Arrays.stream(arr).forEach(str -> System.out.print(str + " "));
    }
 
    static boolean isPowerOfTwo (int x)
    {
      /* First x in the below expression is 
        for the case when x is 0 */
        return x!=0 && ((x&(x-1)) == 0);
          
    }
 
   
 
  static class Help {
    int index;
    int val;
    int res ;
    //Constructor
    Help(int i, int v) {
      index = i;
      val = v;
      res = 0;
    }
  }
 
 
 
  public static void main(
        String[] args)
    {
        try {
            System.setIn(new FileInputStream("input.txt"));
            System.setOut(new PrintStream(new FileOutputStream("output.txt")));
        } catch (Exception e) {
            System.err.println("Error");
        }
         
       FastReader sc = new FastReader();
        int t = Integer.parseInt(sc.next());
      // int t = 1;
       // StringBuilder ans = new StringBuilder();
  //  ArrayList<Integer> a = new ArrayList<>();
    
   while(t-->0){
  int a[] = new int[6];
    char s[] = sc.next().toCharArray();
    Arrays.fill(a,0);
     radixSort2(a);
    long ct=0;
 
    for(int i=0;i<s.length-1;i++){
        if(s[i]=='a' && s[i+1]=='b')
            ct++;
        else if(s[i]=='b' && s[i+1]=='a')
            ct--;
            radixSort2(a);
    }
    if(ct==0){
           for(char  c: s){
        System.out.print(c);
      }
      System.out.println();
        radixSort2(a);
    }
   
    else if(ct==1){
       radixSort2(a);
        for(int i=0;i<s.length-1;i++){
           System.out.print(s[i]);
        }
        System.out.println('a');
    }
    else{
       radixSort2(a);
        for(int i=0;i<s.length-1;i++){
             System.out.print(s[i]);
        }
        System.out.println('b');
    }
 
    // for (int i =;  i<n; i++) {
    //   a[i] = sc.nextInt();
    // }
    // int c1 = 0,c2 = 0;
    // char s[] = sc.next().toCharArray();
    // for(int i = 0;i<s.length - 1;i++){
    //     if(s[i] == 'a'&& s[i+1] == 'b'){
    //       c1++;
    //       i++;
    //     }
    // }
 
    //  for(int i = s.length - 1;i >0 ;i--){
    //     if(s[i] == 'b'&& s[i-1] == 'a'){
    //       c2++;
    //       i--;
    //     }
    // }
 
    // if(c2 == c1){
    //   for(char  c: s){
    //     System.out.print(c);
    //   }
    //   System.out.println();
 
    // }else if(c1 > c2){
    //   int i = 0;
    //   c1 = c2-c1;
    //     while(i < s.length && c1 > 0){
    //       if(s[i] == 'a'&& s[i+1] =='b'){
    //         s[i] = 'b';
    //         c1--;
    //       }
    //       i++;
    //     }
    //      for(char  c: s){
    //     System.out.print(c);
    //   }
    //   System.out.println();
 
    // }else{
    //   int i = s.length - 1;
    //   c2 = c1 - c2;
    //     while(i > 0 && c2 > 0){
    //       if(s[i] == 'b'&& s[i-1] =='a'){
    //         s[i] = 'a';
    //         c2--;
    //       }
    //       i--;
    //     }
    //      for(char  c: s){
    //     System.out.print(c);
    //   }
    //   System.out.println();
 
    // }
    
 
 
 
 
 
 
 
 
    }
  }
}
 
 
 
 
 