D. Dreamoon любит строки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Dreamoon любит строки. Сегодня он придумал игру про строки:

Строка $$$s_1, s_2, \ldots, s_n$$$ красивая если и только если для всех $$$1 \le i < n, s_i \ne s_{i+1}$$$.

Исходно, у Dreamoon есть строка $$$a$$$. За один ход Dreamoon может выбрать красивую подстроку $$$a$$$ и удалить ее. Затем он должен сконкатенировать оставшиеся символы (в правильном порядке).

Dreamoon хочет использовать минимальное число ходов, чтобы сделать $$$a$$$ пустой. Пожалуйста, помогите Dreamoon, и выведите любую последовательность, состоящую из минимального числа ходов, чтобы сделать $$$a$$$ пустой.

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

В первой строке записано целое число $$$t$$$ ($$$1 \leq t \leq 200\,000$$$), равное количество наборов входных данных.

Каждый набор входных данных содержит одну строку $$$a$$$ из строчных латинских символов.

Гарантируется, что суммарный размер строк не превосходит $$$200\,000$$$.

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

Для каждого набора входных данных, в первой строке вы должны вывести $$$m$$$: минимальное количество ходов, чтобы сделать $$$a$$$ пустой. Каждая из следующих $$$m$$$ строк должна содержать два целых числа $$$l_i, r_i$$$ ($$$1 \leq l_i \leq r_i \leq |a|$$$), описывающих, что на $$$i$$$-м шагу нужно удалить символы с индексами от $$$l_i$$$ до $$$r_i$$$ из исходной строки. (Индексы пронумерованы начиная с $$$1$$$).

Обратите внимание, что после удаления подстроки, индексы оставшихся символов могут измениться, и $$$r_i$$$ не должен превышать текущий размер $$$a$$$.

Если есть несколько возможных решений, вы можете вывести любое.

Пример
Входные данные
4
aabbcc
aaabbb
aaa
abacad
Выходные данные
3
3 3
2 4
1 2
3
3 4
2 3
1 2
3
1 1
1 1
1 1
1
1 6