Возможно, некоторым из вас знакома игра Zuma о приключениях лягушки. В данной задаче правила похожи и довольно просты: в каменном жёлобе находится ряд разноцветных шаров; пушка, расположившаяся рядом с жёлобом, имеет некоторый запас разноцветных шаров и периодически закидывает их в желоб. Заброшенные шары встраиваются в ряд. Если после выстрела в желобе образуется непрерывная последовательность из трех или более шаров одного цвета, включающая заброшенный шар, то они исчезают, а соседние шары сдвигаются, смыкая ряд (см. рис. ниже). Если после исчезновения шаров в месте стыка соседние шары образуют непрерывную последовательность из трех или более шаров одного цвета, то они также исчезают, и так далее. Цель игры – уничтожить все шары.

   Пронумеруем шары слева направо, начиная с единицы. Выстрел шара в позицию n означает, что он появится правее шара с номером n и окажется в позиции n+1. Номера шаров, расположенных правее прилетевшего шара, увеличиваются на единицу. Приземление шара левее всего ряда обозначается позицией с номером 0. После исчезновения некоторых шаров, шары в желобе нумеруются заново слева направо, начиная с единицы.

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

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

   Первая строка входа содержит количество тестов. Каждый тест состоит из одной строки с описанием одного ряда шаров, цвет каждого шара описывается заглавной буквой латинского алфавита (A..Z). Тест №1 и его решение изображен на иллюстрации. Известно, что длина ряда ≤ 14, а для уничтожения ряда требуется ≤ 10 выстрелов, если следовать оптимальной стратегии.

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

   Для каждого теста в выходной файл вывести строку: сначала минимальное количество выстрелов, затем через пробел пары буква-число: цвет шара и позицию выстрела. Выстрелы в ответе должны быть в перечислены в порядке их следования в игре.