Циклічним зсувом рядка називається рядок, який отримується з вихідного переміщенням декількох перших символів в кінець рядка. Ваша задача - по заданому рядку знайти його лексикографічно мінімальний циклічний зсув.
У першому рядку вхідного файлу міститься число k - кількість тестів. Далі у k рядках містяться самі рядки. Кожен рядок містить символи з кодами від 33 до 126. Розмір вхідного файла не буде перевищувати одного мегабайта.
Для кожного з тестів виведіть один рядок - найменший циклічний зсув.