Гра Zuma
Можливо, деяким з вас знайома гра Zuma про пригоди жабки. У даній задачі правила схожі і досить прості: в каме'яноу жолобі знаходиться ряд різнокольорових кульок; гармата, роміщена поруч з жолобом, має деякий запас різнокольорових куль і періодично закидає їх у жолоб. Закинуті кулі вистроюються в ряд. Якщо після пострілу в жолобі утворюється неперервна послідовність з трьох або більше куль одного кольору, включаючи закину кулю, то вони зчезають, а сусідні кулі здвигаються, змикаючи ряд (див. рис. нижче). якщо після зчезнення куль у місці стику сусідні кулі утворюють неперервну послідовність з трьох або більше куль одного кольору, то вони також зчезають, і так далі. Мета гри – знищити всі кулі.
Пронумеруємо кулі зліва направо, починаючи з одиниці. Постріл кулі в позицію n означає, що він появиться правіше кулі з номером n і виявиться в позиції n+1. Номери куль, розміщених правіше прилетівшої кулі, збільшуються на одиницю. Приземлення кулі лівіше всього ряду позначається позицією з номером 0. Після зникнення деяких куль, кулі в жолобі нумеруються заново зліва направо, починаючи з одиниці.
Потрібно написати програму, яка визначає оптимальну стратегію стрільби. Оптимальною стратегією називається та, при якій найменша кількість пострілів призводить до зчезненню всіх куль, а якщо таких стратегій декілька, то вибирається та, при якій першй постріл робиться якомого лівіше, а якщо декілька і таких, то порівняння йде за другим пострілом і т.д.
Вхідні дані
Перший рядок містить кількість тестів. Кожен тест складається з одного рядка з описом одного ряду куль, колір кожної кулі описується велткою літерою латинського алфавіту (A..Z). Тест №1 і його розв'язок зображено на ілюстрації. Відомо, що довжина ряду ≤ 14, а для знищення ряду потрібно ≤ 10 пострілів, якщо притримуватись оптимальної стратегії.
Вихідні дані
Для кожного тесту вивести рядок: спочатку мінімальну кількість пострілів, а потім через пропуск пари буква-число: колір кулі і позицію пострілу. постріли у відповіді повинні бути перераховані у порядку їх виконання у грі.