You are given a string of lowercase characters. Your task is to rearrange (reorder) the string in such a way that no two adjacent characters are the same.

You have to return the rearranged string. If there exists more than one solution you can return any of them.If there is no such string you have to return “NO SOLUTION”. If your returned value is correct the program will print ‘CORRECT’ else ‘INCORRECT’.

For example :

If we are given a string "aabb", then the possible solutions are:

(i) abab
(ii) baba

We can see no two adjacent characters are the same in both strings.

So both (i) and (ii) are valid solutions.

Input Format:

The first line of input contains a single integer 'T', representing the number of test cases.

The first and only line of each test case contains a string 'STR'.

Output format:

For each test case, return the resultant string if it is possible to rearrange string else return "NO SOLUTION". Accordingly, CORRECT or INCORRECT will get printed on the screen.

Note

You don’t have to print anything, it has already been taken care of. Just implement the given function. 

Constraints:

1 <= T <= 100
1 <= N <= 10^4

Where ‘N’ is the length of the string.

Time limit: 1 sec