Наименьший циклический сдвиг

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

Входные данные

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

Выходные данные

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

Примеры