Пег Солітер#6035
Гра в пег-солітер, популярна при дворі французького короля Людовіка XIV, має такі правила. Дошка являє собою двовимірну сітку з отворами, кожен з яких може містити один пег (штифт). Єдиний дозволений хід пега — це вертикальний або горизонтальний стрибок через сусідній пег у порожній отвір, що знаходиться поруч із перестрибнутим пегом на одній лінії з ним, після чого перестрибнутий пег видаляється. Початкова мета гри полягала в тому, щоб залишити один пег у заздалегідь визначеній позиції на дошці, виконуючи лише дозволені ходи.
Очевидно, таке рішення можливе лише для певних форм дошки та початкових конфігурацій. Щоб зняти це обмеження, ми трохи переозначимо задачу: враховуючи початкову конфігурацію дошки, визначте мінімальну кількість пегів, яку можна залишити за допомогою дозволених ходів, а також мінімальну кількість ходів, необхідних для досягнення цієї кількості пегів.
Перший рядок містить кількість тестових випадків (1 \le n \le 100). Кожен тестовий випадок описується наступними рядками, які представляють початковий стан дошки солітера. У цьому представленні '.' позначає порожній отвір, а 'o' — отвір з пегом у ньому. '#' вказує на частину дошки без отвору. Усі дошки мають однакову форму, див. приклад вхідних даних (що включає положення отворів). У своєму початковому стані дошка може містити не більше пегів. Між двома послідовними тестовими випадками є порожній рядок.
Для кожного тестового випадку ваша програма повинна вивести рядок з двома числами, розділеними одним пробілом, де перше позначає мінімальну кількість пегів, досяжну дозволеними ходами, починаючи з даного початкового стану, а друге надає мінімально необхідну кількість ходів.
Приклад 1