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