Grovyle String
Tag(s):

## Very-Easy

Problem
Editorial
Analytics

Trico is trying to impress a girl. But the girl is not showing any sign of interest to him. So his best friend suggested him to gift one Grovyle string to her. Grovlye string is a odd length string consisting of only lowercase alphabets arranged in such a way that a number X associated with it is smallest as possible.

X is calculated as : First take absolute distance of each character's position from the center of the string i.e., (string length/2) and then multiply the distance with its ASCII value. Similarly find all the values and add them.

Example : Given string : aaa

Here only one unique permutation is possible : aaa

distances are : for first a, d1 = 1, second a, d2 =0, third a, d3 = 1;

so X = 1 X 97 + 0 X 97 + 1 X 97 = 194;

So given a string of odd length consisting of only lowercase alphabets, find one permutation of the given string such that X is smallest as possible. And if there are many such strings then print the lexicographically smallest one.

Input: First line contains T, the number of test cases that follow. Next T lines, each contains one odd length string consisting of only lowercase alphabets.

Output: For each test case, print the desired result in separate lines.

Constraints: 1 ≤ T ≤ 1000 0 ≤ String Length ≤ 1001

Setter : Sourav Kumar Paul

SAMPLE INPUT
2
aaa
abc
SAMPLE OUTPUT
aaa
acb
Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...