Kindly complete the function magical_string(), strictly in Python3 language only.

consider the constraints as well as multiple hidden test cases need to be passed

Magical string You are given the following: . S String consisting of only uppercase English alphabets You want to convert string Sinto a Magical string that has either of the following properties! All the characters in the string consist of either A or B. . There exists index/such that 1 Si N and all the characters at indices less than or equal to i are A and all the characters at indices greater than /are B or vice-versa. Task Determine the magical string which is of maximum length and is Rexicographically smallest. If there exists no such string, print Impossible. Notes . String p is lexicographically smaller than string g, if pis a prefix of q, is not equal to g or there exists such that p, q, and for all yis satisfied that po. For example, aab is lexicographically smaller than aabb. afa is not lexicographically smaller than ab. l-based indexing is followed. Example Assumption Assumption . S = "ABCDABS" Approach Delete characters at indices S2, S3, S4, S, The resultant string S = "AAB". Therefore, the answer is AAB. Function description Complete the magical string function provided in the editor. This function takes the following parameter and returns the answer: . S. Represents the given string Input format Note: This is the input format that you must use to provide custom input (available above the Compile and Test button) . The first line contains an integer T denoting the number of test cases. Talso denotes the number of times you have to run the magical string function on a different set of inputs. For each test case: The first line contains a string S. Output format Output format For each test case, print the output in a new line. Constraints 1ST