Дано рядок ~S = s_1 , s_2 , ...s_n~ . Вам потрiбно зробити з ним один танцювальний рух такий, щоб вiн став лексикографiчно найменшим. Пiд танцювальним рухом будемо розумiти рiвно один розворот пiдрядка в рядку ~S~.

Формально кажучи, необхiдно вибрати пару iндексiв ~x, y~ ~(1 \le x \le y \le n)~, а потiм змiнити порядок символiв з iндексами вiд ~x~ до ~y~ включно на протилежний. Тобто пiдрядок ~s_x , s_{x+1} ...s_y~ замiнюється на ~s_y , s_{y-1} , ...s_x ~.

Ваша мета — отримати лексикографiчно найменший рядок iз можливих.

Формат вхідних даних

Перший рядок мiстить кiлькiсть ~T~ ~(1 \le T \le 10^5 )~ наборiв вхiдних даних. Кожний набiр вхiдних даних розташований в окремому рядку вхiдного потоку i складається з одного непустого рядка ~S~. Кожен символ рядку ~S~ — мала буква англiйського алфавiта (вiд ~a~ до ~z~). Сума довжин рядкiв ~S~ по всiм наборам вхiдних даних не перевищує ~10^6 ~.

Формат вихідних даних

Для кожного набору вхiдних даних виведiть один рядок з двома цiлими числами ~x~ i ~y~. Якщо iснує декiлька оптимальних варiантiв вiдповiдей, виведiть будь-який iз них.

Приклад вхідних даних

1
abacaba

Приклад вихідних даних

2 7