String Rearrangement Problem Statement

You are given a string of lowercase characters. The objective is to rearrange (reorder) the string so that no two adjacent characters are identical.

Return the rearranged string. If multiple solutions exist, you can return any of them. If no such rearrangement is possible, return “NO SOLUTION”. If your returned value is correct, the program will output ‘CORRECT’; otherwise, it will output ‘INCORRECT’.

Example:

Input:

str = "aabb"

Output:

"abab" or "baba"

Constraints:

• 1 <= T <= 100, where T is the number of test cases.
• 1 <= N <= 10^4, where N is the length of the string.
• Time limit: 1 second.

Input:

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:

For each test case, return the rearranged string if possible; otherwise, return "NO SOLUTION". CORRECT or INCORRECT will be displayed based on the validity of your output.

Note:

You do not have to print anything. Just implement the function as specified.