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

// package template;

import java.util.*;
import java.io.*;

public class Template {

		public 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 nextLong() {
				return Long.parseLong(next());
			}
		}
		
		//prime sieve
		public static boolean sieve[];
		public static void sievePrime(int n) {
			sieve = new boolean[n+1];
			for (int i = 0; i <= n; i++)
	            sieve[i] = true;
	 
	        for (int p = 2; p * p <= n; p++)
	        {
	            // If prime[p] is not changed, then it is a
	            // prime
	            if (sieve[p] == true)
	            {
	                // Update all multiples of p
	                for (int i = p * p; i <= n; i += p)
	                    sieve[i] = false;
	            }
	        }
	 
	       
			
		}
		
		
		public static boolean isPrime(int n)
		{
			boolean flag = true;
			for(int i = 2;i*i<=n;i++)
			{
				if(n%i==0)
				{
					flag = false;
					break;
				}
			}
			
			return flag;
		}
		
		//swap
		public static void swap(int a,int b) {
			int temp= a;
			a=b;
			b=temp;
		}
		
		//Longest Palindromic String
		 public String manacher(String s){
		        StringBuilder sb = new StringBuilder();
		        sb.append("@");
		        for(int i=0;i<s.length();i++){
		            sb.append("#");
		            sb.append(s.charAt(i));
		        }
		        sb.append("#");
		        sb.append("$");
		        String ans = manacher_Util(sb.toString(),s);
		        return ans;
		    }
		    public String manacher_Util(String s,String org){
		        int lps[] = new int[s.length()];
		        int c = 0;
		        int r = 0;
		        for(int i=1;i<s.length()-1;i++){
		            int mirror = c - (i-c);
		            if(i<r){
		                lps[i] = Math.min(lps[mirror],r-i);
		            }
		        
		            while(s.charAt(1+i+lps[i]) == s.charAt(i-1-lps[i])){
		                lps[i]++;
		            }
		            if(i+lps[i] > r){
		                c= i ;
		                r = i+lps[i];
		            }
		        }
		        int maxlen = Integer.MIN_VALUE;
		        int maxindex = Integer.MIN_VALUE;
		        for(int i=1;i<lps.length-1;i++){
		            if(lps[i] > maxlen){
		                maxlen = lps[i];
		                maxindex = i;
		            }
		        }
		        int firstindex = maxindex - maxlen + 1;
		        int actualFirstIndex = (firstindex-2)/2;
		        return org.substring(actualFirstIndex,actualFirstIndex+maxlen);
		    }
		
		
		    //kmp
		    public static int lps[];
		    public static void kmp(String s) {
		    	lps = new int[s.length()];
		    	int i = 1;
		    	int len = 0;
		    	while(i<s.length()) {
		    		if(s.charAt(i) == s.charAt(len)) {
		    			len++;
		    			lps[i] = len;
		    			i++;
		    		}
		    		else {
		    			if(len>0) {
		    				len = lps[len - 1];
		    			}
		    			else {
		    				lps[i] = 0;
		    				i++;
		    			}
		    		}
		    	}
		    }

		public static void main(String[] args) {
		    FastScanner sc = new FastScanner();
			int test = sc.nextInt();
			PrintWriter o = new PrintWriter(System.out);
		
			
			while(test-->0) {
				
				String s = sc.next();
				StringBuilder sb = new StringBuilder(s);
				int cn = 0;
				for(int i = 1;i<s.length();i++)
				{
					if(s.charAt(i)!=s.charAt(i-1))
					{
						cn++;
					}
				}
				if(cn%2==0)
				{
					o.println(s);
				}else {
					if(s.charAt(0)=='a')
					{
						for(int i = s.length()-1;i>=0;i--)
						{
							if(s.charAt(i)=='b')
							{
								sb.setCharAt(i, 'a');
								break;
							}
						}
						o.println(sb);
					}else {
						for(int i = s.length()-1;i>=0;i--)
						{
							if(s.charAt(i)=='a')
							{
								sb.setCharAt(i, 'b');
								break;
							}
						}
						o.println(sb);
					}
				}
				
			}
			o.close();
			
		}
		
		static ArrayList<String> solve(int n)
		{
			ArrayList<String> a = new ArrayList<>();
			int close = n;
			int open = n;
			String op = "";
			r(open,close,op,a);
			for(int i = 0;i<n;i++)
			{
				System.out.println(a.get(i));
			}
			return a;
		}
		static void r(int open ,int close,String op,ArrayList<String> a)
		{
			if(open==0 && close ==0)
			{
				a.add(op);
				return;
			}
			
			if(open!=0)
			{
				String op1 = op;
				op1 = op1 +"(";
				r(open-1,close,op1,a);
			}
			if(close>open)
			{
				String op2 = op;
				op2 = op2 +")";
				r(open,close-1,op2,a);
			}
		}
		
		static int gcd(int a, int b)
	    {
	      if (b == 0)
	        return a;
	      return gcd(b, a % b);
	    }
		
		public static int fac(int n)
		{
			int ans = 1;
			for(int i = 1;i<=n;i++)
			{
				ans *= i;
			}
			return ans;
		}
		
	}

class pair{
	int value;
	int index;
	pair(int value,int index){
		this.value= value;
		this.index=index;
	}
	public int getValue() {
		return value;
	}
	public void setValue(int value) {
		this.value = value;
	}
	public int getIndex() {
		return index;
	}
	public void setIndex(int index) {
		this.index = index;
	}
}