输入由小写字母组成的字符串(保证其中的字符各不相同)，找出其中最小的字符，将它与串首字符交换后输出。

Input

输入数据首先包含一个整数T，表示测试实例的个数，然后是T组测试数据。每组占一行。

Output

对于每组输入数据，输出交换后的字符串，每组输出占一行。

Sample Input

3
qwerty
asdfg
zxcvbnf

Sample Output

ewqrty
asdfg
bxcvznf