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.*;
 
public class Solution{
static FastScanner sc = new FastScanner();
public static void solve() {
  String s=sc.next();
  char[] c=s.toCharArray();
  int ct1=0,ct2=0,c1=0,c2=0;
  int n=c.length;
  for (int i=0;i<n-1;i++) {
    if (c[i]=='a' && c[i+1]=='b') {
      ct1++;
    }
    if(c[i]=='b' && c[i+1]=='a'){
      ct2++;
    }
    if (c[i]=='a') {
      c1++;
    }else{
      c2++;
    }
  }
  // if (c[n-1]=='a') {
  //   c1++;
  // }else{
  //   c2++;
  // }
  if (ct1==ct2) {
    System.out.println(s);
    return ;
  }
  
      if(ct1>ct2)
      {
        for(int i=0;i<s.length();i++){
          if(c[i]=='a')
            c[i]='b';
          break;
        }
      }
      else
      {
        for(int i=0;i<s.length();i++){
          if(c[i]=='b')
            c[i]='a';
          break;
        }
 
      }
      System.out.println(new String(c));
 
    }
    

public static void main(String[] args) {
  int t = sc.nextInt();
  // int t=1;
  outer: for (int tt = 0; tt < t; tt++) {
    solve();
  }

}
static boolean isPrime(int n)
    {
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
  
        if (n % 2 == 0 || n % 3 == 0)
            return false;
  
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
  
        return true;
    }
public static int[] LPS(String s){
  int[] lps=new int[s.length()];
  int i=0,j=1;
  while (j<s.length()) {
    if(s.charAt(i)==s.charAt(j)){
      lps[j]=i+1;
      i++;
      j++;
      continue;
    }else{
      if (i==0) {
        j++;
        continue;
      }
      i=lps[i-1];
      while(s.charAt(i)!=s.charAt(j) && i!=0) {
        i=lps[i-1];
      }
      if(s.charAt(i)==s.charAt(j)){
      lps[j]=i+1;
      i++;
      }
      j++;
    }
  }
  return lps;
}
static long getPairsCount(int n, double sum,int[] arr)
    {
        HashMap<Double, Integer> hm = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (!hm.containsKey((double)arr[i]))
                hm.put((double)arr[i], 0);
            hm.put((double)arr[i], hm.get((double)arr[i]) + 1);
        }
        long twice_count = 0;
        for (int i = 0; i < n; i++) {
            if (hm.get(sum - arr[i]) != null)
                twice_count += hm.get(sum - arr[i]);
            if (sum - (double)arr[i] == (double)arr[i])
                twice_count--;
        }
        return twice_count / 2l;
    }
static boolean[] sieveOfEratosthenes(int n)
    {
        boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;
 
        for (int p = 2; p * p <= n; p++)
        {
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        return prime;
 }
static long power(long x, long y, long p)
  {
    long res = 1l; 
    x = x % p;
    if (x == 0)
      return 0;
    while (y > 0)
    {

      if ((y & 1) != 0)
        res = (res * x) % p;
      y>>=1;
      x = (x * x) % p;
    }
    return res;
  }

public static int log2(int N)
    {
        int result = (int)(Math.log(N) / Math.log(2));
  
        return result;
    }

////////////////////////////////////////////////////////////////////////////////////
////////////////////DO NOT READ AFTER THIS LINE //////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////
static long modFact(int n, 
                       int p) 
    { 
        if (n >= p) 
            return 0; 
      
        long result = 1l; 
        for (int i = 3; i <= n; i++) 
            result = (result * i) % p; 
      
        return result; 
    } 
      
static boolean isPalindrom(char[] arr, int i, int j) {
  boolean ok = true;
  while (i <= j) {
    if (arr[i] != arr[j]) {
      ok = false;
      break;
    }
    i++;
    j--;
  }
  return ok;
}

static int max(int a, int b) {
  return Math.max(a, b);
}

static int min(int a, int b) {
  return Math.min(a, b);
}

static long max(long a, long b) {
  return Math.max(a, b);
}

static long min(long a, long b) {
  return Math.min(a, b);
}

static int abs(int a) {
  return Math.abs(a);
}

static long abs(long a) {
  return Math.abs(a);
}

static void swap(long arr[], int i, int j) {
  long temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

static void swap(int arr[], int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

static int maxArr(int arr[]) {
  int maxi = Integer.MIN_VALUE;
  for (int x : arr)
    maxi = max(maxi, x);
  return maxi;
}

static int minArr(int arr[]) {
  int mini = Integer.MAX_VALUE;
  for (int x : arr)
    mini = min(mini, x);
  return mini;
}

static long maxArr(long arr[]) {
  long maxi = Long.MIN_VALUE;
  for (long x : arr)
    maxi = max(maxi, x);
  return maxi;
}

static long minArr(long arr[]) {
  long mini = Long.MAX_VALUE;
  for (long x : arr)
    mini = min(mini, x);
  return mini;
}
static int lcm(int a,int b){
  return (int)(((long)a*b)/(long)gcd(a,b));
}
static int gcd(int a, int b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

static long gcd(long a, long b) {
  if (b == 0)
    return a;
  return gcd(b, a % b);
}

static void ruffleSort(int[] a) {
  int n = a.length;
  Random r = new Random();
  for (int i = 0; i < a.length; i++) {
    int oi = r.nextInt(n);
    int temp = a[i];
    a[i] = a[oi];
    a[oi] = temp;
  }
  Arrays.sort(a);
}

public static int binarySearch(int a[], int target) {
  int left = 0;
  int right = a.length - 1;
  int mid = (left + right) / 2;
  int i = 0;
  while (left <= right) {
    if (a[mid] <= target) {
      i = mid + 1;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
    mid = (left + right) / 2;
  }
  return i-1;
}


static class FastScanner {
  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  StringTokenizer st = new StringTokenizer("");

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

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

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

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

  int[][] read2dArray(int n, int m) {
    int arr[][] = new int[n][m];
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        arr[i][j] = nextInt();
      }
    }
    return arr;
  }

  ArrayList<Integer> readArrayList(int n) {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    for (int i = 0; i < n; i++) {
      int a = nextInt();
      arr.add(a);
    }
    return arr;
  }

  long nextLong() {
    return Long.parseLong(next());
  }
}
 static class Pair {
  int l, r;

  Pair(int fr, int sc) {
    this.l = fr;
    this.r = sc;
  }
}
}