Пег Солитер
Игра в пег-солитер, популярная при дворе французского короля Людовика XIV, имеет следующие правила. У вас есть двумерная доска с сеткой отверстий, каждое из которых может содержать одну пегу (штырь). Единственный допустимый ход пеги — это вертикальный или горизонтальный прыжок через соседнюю пегу в пустое отверстие, расположенное на одной линии с перепрыгнутой пегой, после чего перепрыгнутая пега удаляется. Изначальная цель игры состояла в том, чтобы оставить одну пегу в заранее определенной позиции на доске, выполняя только допустимые ходы.
Очевидно, такое решение возможно только для определенных форм доски и начальных конфигураций. Чтобы снять это ограничение, мы слегка изменяем задачу: дано начальное расположение на доске, необходимо определить минимальное количество пег, которое можно оставить, выполняя допустимые ходы, а также минимальное количество ходов, необходимых для достижения этого количества пег.
Входные данные
Первая строка содержит количество тестов n (1 ≤ n ≤ 100). Каждый тест описывается следующими строками, представляющими начальное состояние доски для солитера. В этом представлении '.' обозначает пустое отверстие, а 'o' — отверстие с пегой. '#' указывает часть доски без отверстия. Все доски имеют одинаковую форму, см. пример входных данных (включая расположение отверстий). В начальном состоянии на доске может быть не более 8 пег. Между двумя последовательными тестами имеется пустая строка.
Выходные данные
Для каждого теста ваша программа должна вывести строку с двумя числами, разделенными одним пробелом, где первое обозначает минимальное количество пег, достижимое допустимыми ходами, начиная с данного начального состояния, а второе — минимальное необходимое количество ходов.