Найменший циклічний зсув

Циклічним зсувом рядка називається рядок, який отримується з вихідного переміщенням декількох перших символів в кінець рядка. Ваша задача - по заданому рядку знайти його лексикографічно мінімальний циклічний зсув.

Вхідні дані

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

Вихідні дані

Для кожного з тестів виведіть один рядок - найменший циклічний зсув.

Приклади