100000048 - Round 843 1775A2 园丁和海豚
将一个仅由'a','b'构成的字符串s从左到右分割为非空的3部分：a,b,c，使得按字典序b不大于a,c或不小于a,c。
Input
第一行，一个整数t。
接下来t行，每行一个长度大于2小于2×10^5的仅由小写'a','b'构成的字符串。
Output
每行数据数据一行，表示从左到右分割的结果。
Examples
Input
5 bbba aba aaa abba abbb
Output
b bb a a b a a a a ab b a a bb b