You are given a stirng S. Find its lexicographically minimal shift. String S1 is called 'shift of string S' if it can be achieved from string S by repeating the following steps arbitrary number of times: 1. Append first letter of S to S. 2. Remove first letter from S. Input data specification First string of the file contains number of test cases T. Then for each of T cases there's one line containing string S. Output data specification For each test case produce one line of output with lexicographically minimal shift of string S. Constrains: 1 <= Lenght of S <= 30000 S consists only of lowercase english letters and digits Sample input: 2 baab abrakadabra Sample output: aabb aabrakadabr