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\) пустой.
Выходные данные
Для каждого набора входных данных, в первой строке вы должны вывести \(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\).
Если есть несколько возможных решений, вы можете вывести любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|