Возможно, некоторым из вас знакома игра Zuma о приключениях лягушки. В данной задаче правила похожи и довольно просты: в каменном жёлобе находится ряд разноцветных шаров; пушка, расположившаяся рядом с жёлобом, имеет некоторый запас разноцветных шаров и периодически закидывает их в желоб. Заброшенные шары встраиваются в ряд. Если после выстрела в желобе образуется непрерывная последовательность из трех или более шаров одного цвета, включающая заброшенный шар, то они исчезают, а соседние шары сдвигаются, смыкая ряд (см. рис. ниже). Если после исчезновения шаров в месте стыка соседние шары образуют непрерывную последовательность из трех или более шаров одного цвета, то они также исчезают, и так далее. Цель игры -- уничтожить все шары. \includegraphics{https://static.e-olymp.com/content/34/349211fbad9306b9a1130bc8437914d0ee00d05f.jpg} Пронумеруем шары слева направо, начиная с единицы. Выстрел шара в позицию \textbf{n} означает, что он появится правее шара с номером \textbf{n} и окажется в позиции \textbf{n+1}\textit{.} Номера шаров, расположенных правее прилетевшего шара, увеличиваются на единицу. Приземление шара левее всего ряда обозначается позицией с номером \textbf{0}. После исчезновения некоторых шаров, шары в желобе нумеруются заново слева направо, начиная с единицы. Требуется написать программу, определяющую оптимальную стратегию стрельбы. Оптимальной стратегией называется та, при которой наименьшее количество выстрелов приводит к исчезновению всех шаров, а если таких стратегий несколько, то выбирается та, при которой первый выстрел производится как можно левее, а если несколько и таких, то сравнение идёт по второму выстрелу и т.д. \InputFile Первая строка содержит количество тестов. Каждый тест состоит из одной строки с описанием одного ряда шаров, цвет каждого шара описывается заглавной буквой латинского алфавита (\textbf{A}..\textbf{Z}). Тест №\textbf{1} и его решение изображен на иллюстрации. Известно, что длина ряда ≤ \textbf{14}, а для уничтожения ряда требуется ≤ \textbf{10} выстрелов, если следовать оптимальной стратегии. \OutputFile Для каждого теста вывести одну строку: сначала минимальное количество выстрелов, затем через пробел пары буква-число: цвет шара и позицию выстрела. Выстрелы в ответе должны быть в перечислены в порядке их следования в игре.