Знаменитый менеджер аэропорта
Мистер B - менеджер в аэропорту. Однажды после ланча он выглянул из окна своего офиса и обнаружил, что цвет каждого самолета, находившегося в аэропорту, был либо синим, либо зеленым. Перед ужином он посмотрел на аэропорт снова и не обнаружил там ни одного самолета. Он не мог припомнить порядка, в котором самолеты взлетали, но он точно помнит что между двумя его наблюдениями ни один самолет в аэропорт не прилетел. Когда один самолет движется к взлетной полосе, остальные самолеты нахожятся на своих начальных местах и не двигаются. Другими словами, если рассматривать порядок взлета, то сначала первый самолет движется к взлетной полосе, а все остальные стоят на своих местах. После того как первый самолет улетел, второй самолет движется к месту взлета и так далее, пока все самолеты не улетят. Мистер B хочет определить количество различных возможных цветных последовательностей, котороые он мог бы наблюдать, если бы он находился на взлетной полосе весь день.
Аэропорт может быть разделен на 9 квадратных областей (3 строки x 3 колонки), в каждой области может быть припарковано не более одного самолета. Область, которая находится в первой колонке и первой строке, называется "зоной взлета". Самолет может взлететь только в "зоне взлета". Кроме того, каждый самолет (включая тот что находится в зоне взлета) может передвигаться в свободную соседнюю область. Две области считаются сосседними, если у них имеется общая граница.
Входные данные
Каждый тест состоит из 3 строк, каждая из которых содержит по 3 символа '*', 'B', 'G', указывающих на тот факт, что соответствующее место в аэропорту соответственно либо пустое, либо занято синим или зеленым самолетом. Первый символ первой строки всегда равен '*'. В ангаре имеется как минимум одно место.
Содержит до 30000 тестов. Будьте осторожны!
Выходные данные
Для каждого теста вывести в отдельной строке его номер и количество различных возможных цветных последовательностей, которое мог наблюдать мистер B.