Дано рядок \(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
Коментарі