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.util.StringTokenizer;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Collections;
import java.util.ArrayList;

public class p1
{
	BufferedReader br;
	StringTokenizer st;
	BufferedWriter bw;
	public static void main(String[] args)throws Exception
	{
		new p1().run();
	}

	void run()throws IOException
	{
		br = new BufferedReader(new InputStreamReader(System.in));
		bw=new BufferedWriter(new OutputStreamWriter(System.out));

		solve();
	}
	void solve() throws IOException
	{
		short t=ns();
		while(t-->0)
		{
			char c[]=nac();
			int n=c.length;

			int count=0,a;
			a=c[0]-97;

			for(int i=-1;++i<n;)
			{
				if(c[i]-97!=a)
				{
					a^=1;
					count++;
				}
			}
			
			if(count%2==1)
			{
				c[n-1]-=97;
				c[n-1]^=1;
				c[n-1]+=97;
			}
			for(int i=-1;++i<n;)
			bw.write(c[i]);
			bw.write("\n");;
		}
		bw.flush();
	}






	public int gcd(int a, int b)
	{
		if(a==0)
			return b;
		else
		 return gcd(b%a,a);
	}

	int[] nai(int n) { int a[]=new int[n]; for(int i=-1;++i<n;)a[i]=ni();	return a;}

	long[] nal(int n) { long a[]=new long[n]; for(int i=-1;++i<n;)a[i]=nl();	return a;}

	char[] nac()	{char c[]=nextLine().toCharArray();	return c;}

	char [][] nmc(int n)	{char c[][]=new char[n][]; for(int i=-1;++i<n;)c[i]=nac();	return c;}

	int[][] nmi(int r, int c)	{int a[][]=new int[r][c]; for(int i=-1;++i<r;)a[i]=nai(c);	return a;}

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

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

	byte nb() { return Byte.parseByte(next()); }

	short ns() { return Short.parseShort(next()); }

	long nl() { return Long.parseLong(next()); }

	double nd()	{	return Double.parseDouble(next());	}

	String nextLine()
	{
			String str = "";
			try {
					str = br.readLine();
			}
			catch (IOException e) {
					e.printStackTrace();
			}
			return str;
	}

	int countDigits(int l)	{
		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;
	}
	int countDigits(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 >= 1000000000L) return 10;
		if (l >= 100000000L) return 9;
		if (l >= 10000000L) return 8;
		if (l >= 1000000L) return 7;
		if (l >= 100000L) return 6;
		if (l >= 10000L) return 5;
		if (l >= 1000L) return 4;
		if (l >= 100L) return 3;
		if (l >= 10L) return 2;
		return 1;
	}

	public int[] primeNO(long limit)
	{
		int size=(int)Math.sqrt(limit)+1;
		int size1=size/2;
		boolean composite[]=new boolean[size1];
		int zz=(int)Math.sqrt(size-1);

		for(int i=3;i<=zz;)
		{
			for(int j=(i*i)/2;j<size1;j+=i)
				composite[j]=true;

			for(i+=2;composite[i/2];i+=2);
		}

		int prime[]=new int[3401];
		prime[0]=2;
		int p=1;
		for(int i=1;i<size1;i++)
		{
			if(!composite[i])
				prime[p++]=2*i+1;
		}

		////////////////////////////////////////////////////////////////////////////////////////////////////////
		// System.out.println(p);
		////////////////////////////////////////////////////////////////////////////////////////////////////////
		prime=Arrays.copyOf(prime, p);
		return prime;
	}

	public static class queue
	{
		public static class node
		{
			node next;
			int val;

			public node(int val)
			{
				this.val=val;
			}
		}

		node head,tail;

		public void add(int val)
		{
			node a=new node(val);

			if(head==null)
			{
				head=tail=a;
				return;
			}
			tail.next=a;
			tail=a;
		}

		public int remove()
		{
			int a=head.val;
			head=head.next;
			if(head==null)
				tail=null;

			return a;
		}
	}

	public static class stack
	{
		public static class node
		{
			node next;
			int val;

			public node(int val)
			{
				this.val=val;
			}
		}

		node head;

		public void add(int val)
		{
			node a=new node(val);

			a.next=head;
			head=a;
		}

		public int remove()
		{
			int a=head.val;
			head=head.next;
			return a;
		}
	}

	public static class data
	{
		int a,b;

		public data(int a, int b)
		{
			this.a=a;
			this.b=b;
		}
	}

	public data[] dataArray(int n)
	{
		data d[]=new data[n];
		for(int i=-1;++i<n;)
			d[i]=new data(ni(), ni());

		return d;
	}
}
