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.math.*;import static java.lang.Math.*;import static java.
        util.Map.*;import static java.util.Arrays.*;import static java.util.Collections.*;
import static java.lang.System.*;
public class Main
{
    public void tq()throws Exception
    {
        st=new StringTokenizer(bq.readLine());
        int tq=i();
        sb=new StringBuilder(2000000);
        o:
        while(tq-->0)
        {
            String s=s();
            int n=s.length();
            int a=0;int b=0;
            for(int x=0;x<n-1;x++)
            {
                if(s.charAt(x)=='a'&&s.charAt(x+1)=='b')a++;
                if(s.charAt(x)=='b'&&s.charAt(x+1)=='a')b++;
            }
            if(a==b)sl(s);
            else
            {
                char ar[]=s.toCharArray();
                if(s.charAt(n-1)=='a')ar[n-1]='b';
                else ar[n-1]='a';
                sl(new String(ar));
            }
        }
        p(sb);
    }
    void f(){out.flush();}
    int di[][]={{-1,0},{1,0},{0,-1},{0,1}};
    int de[][]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{-1,1},{1,-1}};
    long mod=1000000007l;int max=Integer.MAX_VALUE,min=Integer.MIN_VALUE;long maxl=Long.MAX_VALUE, minl=Long.
        MIN_VALUE;BufferedReader bq=new BufferedReader(new InputStreamReader(in));StringTokenizer st;
    StringBuilder sb;public static void main(String[] a)throws Exception{new Main().tq();}int[] so(int ar[])
{Integer r[]=new Integer[ar.length];for(int x=0;x<ar.length;x++)r[x]=ar[x];sort(r);for(int x=0;x<ar.length;
                                                                                       x++)ar[x]=r[x];return ar;}long[] so(long ar[]){Long r[]=new Long[ar.length];for(int x=0;x<ar.length;x++)
    r[x]=ar[x];sort(r);for(int x=0;x<ar.length;x++)ar[x]=r[x];return ar;}
    char[] so(char ar[]) {Character
            r[]=new Character[ar.length];for(int x=0;x<ar.length;x++)r[x]=ar[x];sort(r);for(int x=0;x<ar.length;x++)
        ar[x]=r[x];return ar;}void s(String s){sb.append(s);}void s(int s){sb.append(s);}void s(long s){sb.
        append(s);}void s(char s){sb.append(s);}void s(double s){sb.append(s);}void ss(){sb.append(' ');}void sl
        (String s){sb.append(s);sb.append("\n");}void sl(int s){sb.append(s);sb.append("\n");}void sl(long s){sb
        .append(s);sb.append("\n");}void sl(char s) {sb.append(s);sb.append("\n");}void sl(double s){sb.append(s)
;sb.append("\n");}void sl(){sb.append("\n");}int l(int v){return 31-Integer.numberOfLeadingZeros(v);}
    long l(long v){return 63-Long.numberOfLeadingZeros(v);}int sq(int a){return (int)sqrt(a);}long sq(long a)
{return (long)sqrt(a);}long gcd(long a,long b){while(b>0l){long c=a%b;a=b;b=c;}return a;}int gcd(int a,int b)
{while(b>0){int c=a%b;a=b;b=c;}return a;}boolean pa(String s,int i,int j){while(i<j)if(s.charAt(i++)!=
        s.charAt(j--))return false;return true;}boolean[] si(int n) {boolean bo[]=new boolean[n+1];bo[0]=true;bo[1]
        =true;for(int x=4;x<=n;x+=2)bo[x]=true;for(int x=3;x*x<=n;x+=2){if(!bo[x]){int vv=(x<<1);for(int y=x*x;y<=n;
                                                                                                     y+=vv)bo[y]=true;}}return bo;}long mul(long a,long b,long m) {long r=1l;a%=m;while(b>0){if((b&1)==1)
    r=(r*a)%m;b>>=1;a=(a*a)%m;}return r;}int i()throws IOException{if(!st.hasMoreTokens())st=new
        StringTokenizer(bq.readLine());return Integer.parseInt(st.nextToken());}long l()throws IOException
{if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());return Long.parseLong(st.nextToken());}String
s()throws IOException {if (!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());return st.nextToken();}
    double d()throws IOException{if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());return Double.
            parseDouble(st.nextToken());}void p(Object p){out.print(p);}void p(String p){out.print(p);}void p(int p)
{out.print(p);}void p(double p){out.print(p);}void p(long p){out.print(p);}void p(char p){out.print(p);}void
p(boolean p){out.print(p);}void pl(Object p){out.println(p);}void pl(String p){out.println(p);}void pl(int p)
{out.println(p);}void pl(char p){out.println(p);}void pl(double p){out.println(p);}void pl(long p){out.
        println(p);}void pl(boolean p)
{out.println(p);}void pl(){out.println();}void s(int a[]){for(int e:a)
{sb.append(e);sb.append(' ');}sb.append("\n");}
    void s(long a[])
    {for(long e:a){sb.append(e);sb.append(' ')
    ;}sb.append("\n");}void s(int ar[][]){for(int a[]:ar){for(int e:a){sb.append(e);sb.append(' ');}sb.append
        ("\n");}}
    void s(char a[])
    {for(char e:a){sb.append(e);sb.append(' ');}sb.append("\n");}void s(char ar[][])
{for(char a[]:ar){for(char e:a){sb.append(e);sb.append(' ');}sb.append("\n");}}int[] ari(int n)throws
        IOException {int ar[]=new int[n];if(!st.hasMoreTokens())st=new StringTokenizer(bq.readLine());for(int x=0;
                                                                                                          x<n;x++)ar[x]=Integer.parseInt(st.nextToken());return ar;}int[][] ari(int n,int m)throws
        IOException {int ar[][]=new int[n][m];for(int x=0;x<n;x++){if (!st.hasMoreTokens())st=new StringTokenizer
        (bq.readLine());for(int y=0;y<m;y++)ar[x][y]=Integer.parseInt(st.nextToken());}return ar;}long[] arl
        (int n)throws IOException {long ar[]=new long[n];if(!st.hasMoreTokens()) st=new StringTokenizer(bq.readLine())
        ;for(int x=0;x<n;x++)ar[x]=Long.parseLong(st.nextToken());return ar;}long[][] arl(int n,int m)throws
        IOException {long ar[][]=new long[n][m];for(int x=0;x<n;x++) {if(!st.hasMoreTokens()) st=new
        StringTokenizer(bq.readLine());for(int y=0;y<m;y++)ar[x][y]=Long.parseLong(st.nextToken());}return ar;}
    String[] ars(int n)throws IOException {String ar[] =new String[n];if(!st.hasMoreTokens())st=new
            StringTokenizer(bq.readLine());for(int x=0;x<n;x++)ar[x]=st.nextToken();return ar;}double[] ard
        (int n)throws IOException {double ar[] =new double[n];if(!st.hasMoreTokens())st=new StringTokenizer
        (bq.readLine());for(int x=0;x<n;x++)ar[x]=Double.parseDouble(st.nextToken());return ar;}double[][] ard
        (int n,int m)throws IOException{double ar[][]=new double[n][m];for(int x=0;x<n;x++) {if(!st.hasMoreTokens())
    st=new StringTokenizer(bq.readLine());for(int y=0;y<m;y++) ar[x][y]=Double.parseDouble(st.nextToken());}
    return ar;}char[] arc(int n)throws IOException{char ar[]=new char[n];if(!st.hasMoreTokens())st=new
        StringTokenizer(bq.readLine());for(int x=0;x<n;x++)ar[x]=st.nextToken().charAt(0);return ar;}char[][]
arc(int n,int m)throws IOException {char ar[][]=new char[n][m];for(int x=0;x<n;x++){String s=bq.readLine();
    for(int y=0;y<m;y++)ar[x][y]=s.charAt(y);}return ar;}void p(int ar[])
{StringBuilder sb=new StringBuilder
        (2*ar.length);for(int a:ar){sb.append(a);sb.append(' ');}out.println(sb);}void p(int ar[][])
{StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);for(int a[]:ar){for(int aa:a){sb.append(aa);
    sb.append(' ');}sb.append("\n");}p(sb);}void p(long ar[]){StringBuilder sb=new StringBuilder
        (2*ar.length);for(long a:ar){ sb.append(a);sb.append(' ');}out.println(sb);}
    void p(long ar[][])
    {StringBuilder sb=new StringBuilder(2*ar.length*ar[0].length);for(long a[]:ar){for(long aa:a){sb.append(aa);
        sb.append(' ');}sb.append("\n");}p(sb);}void p(String ar[]){int c=0;for(String s:ar)c+=s.length()+1;
    StringBuilder sb=new StringBuilder(c);for(String a:ar){sb.append(a);sb.append(' ');}out.println(sb);}
    void p(double ar[])
    {StringBuilder sb=new StringBuilder(2*ar.length);for(double a:ar){sb.append(a);
        sb.append(' ');}out.println(sb);}void p
        (double ar[][]){StringBuilder sb=new StringBuilder(2*
        ar.length*ar[0].length);for(double a[]:ar){for(double aa:a){sb.append(aa);sb.append(' ');}sb.append("\n")
;}p(sb);}void p(char ar[])
{StringBuilder sb=new StringBuilder(2*ar.length);for(char aa:ar){sb.append(aa);
    sb.append(' ');}out.println(sb);}void p(char ar[][]){StringBuilder sb=new StringBuilder(2*ar.length*ar[0]
        .length);for(char a[]:ar){for(char aa:a){sb.append(aa);sb.append(' ');}sb.append("\n");}p(sb);}void pl
        (int... ar){for(int e:ar)p(e+" ");pl();}void pl(long... ar){for(long e:ar)p(e+" ");pl();}
}