单点时限: 1.0 sec
内存限制: 128 MB
字符串A由a，b，c，d四个字母构成，已知字符串中的字母可以按照下面的规则进行合并。
字符-数字对应表：a：1，b：2，c：3，d：4。字母合并等价于对应数字做加法，再将所得的和对应回字母。如，a与b合并相当于1+2=3，得到c。为了增加难度，甚至可以允许数字和超过4，此时将超出的部分减去4，直至落回到1到4之间。如，b与c合并相当于2+3=5（超过4），又因为5-4=1（落回1到4），因此得到a。
问：对于字符串A，使用上面的合并规则，得到的字典序最小的字符串是什么？
共$T+1$行：
第1行：样例数量$T(1\leq T\leq 1000)$
第2~(T+1)行：每行包含字符串A（由a，b，c，d四个字母构成，长度 $\mathrm{len}(A) \leq 10000$）
$T\times \mathrm{len}(A) \leq 10^6$
共 $T$ 行：每行包含合并后字典序最小的字符串
2 aaaaa ccda
a ba
合并方式：
1. a[aaaa] => [ad] => a
2. [cc]da => [bd]a => ba