Тантрикс - это игра для двух с 56 шестиугольными плитками. Каждая плитка содержит три линии разного цвета. Оба игрока держат в руках по пять плиток и совершают хода, кладя их на игровое поле. На картинке справа изображено состояние игры после укладки девяти плиток.
Линии бывают четырех цветов: красного, зеленого, желтого и синего. Никакие две плитки не идентичны, никакой поворот плитки не симметричен. Плитка во входных данных задается строкой из шести букв, задающих цвета линий по часовой стрелке. Заглавные буквы 'R', 'G', 'Y' и 'B' используются для обозначения красного, зеленого, желтого и синего цвета соответственно.
Ходом в игре называется перемещение одной плитки из рук одного игрока на игровое поле согласно следующим правилам:
Плитку следует класть рядом с одной из уже лежащих.
Совпадающие линии всех касающихся плиток должны иметь одинаковый цвет.
Пустое место, окруженное тремя плитками, называется нишей. Если игрок может положить одну из своих плиток в нишу, то он должен это сделать немедленно. Если имеется несколько ниш и существует несколько способов положить туда плитку, то можно выбрать любой из вариантов укладки.
Не разрешается класть плитку, после которой образуется ниша с тремя линиями одинакового цвета (не существует плитки, которой можно заполнить эту нишу).
Две прилегающие друг к другу плитки, соседствующие с одной нишей, образуют контролируемый ряд. Запрещается укладывать плитки вдоль контролируемого ряда.
Если на игровом поле имеется одна или более ниш, но у игрока нет подходящей плитки, то он может совершить любой другой допустимый ход. Иногда игрок не имеет права положить свою плитку в нишу из-за правила 4.
На рисунке справа проиллюстрированы описанные правила. На поле имеются три ниши. Выделенную плитку нельзя уложить в левую нижнюю нишу, так как в этом случае образуется новая ниша с тремя линиями красного цвета. Темные серые ячейки лежат на контролируемых рядах, образованных нишами; здесь класть плитки запрещено. Если игрок не в состоянии заполнить любую из трех ниш, он может сделать ход в одну из белых ячеек.
Следует найти количество допустимых ходов, которое может совершить игрок, если известны позиции и ориентации уже выложенных на игровое поле плиток, а также плитки, имеющиеся на руках у игрока. Если плитку можно положить в разные места, или ориентировать разными способами, то каждый из таких вариантов укладки считать различным.
Первая строка содержит количество тестов (не более 50).
Каждый тест начинается со строки, содержащей количество плиток n (1 ≤ n ≤ 20) на игровом поле. Следующие n строк содержат координаты и описание этих плиток. Первая буква в описании плитки соответствует линии идущей вверх; цвета остальных линий задаются по ходу часовой стрелки. Следующая строка описывает пять плиток, находящихся в руках у игрока, описание плиток разделено одним пробелом.
Соответствие между ячейками и координатами показано на рисунке справа (игровое поле бесконечно и не ограничено только этими координатами). Все входные плитки корректны и различны. На игровом поле задается позиция, которая реально могла возникнуть в игре. Одна из укладеных плиток имеет координаты 0, 0.
Для каждого теста вывести в отдельной строке одно число: количество допустимых ходов.