Тичу
Тичу - это карточная игра для четырех игроков. Игроки сидят вокруг квадратного стола, у каждого из которого партнером считается сидящий напротив. Игра ведется стандартной колодой карт с четырьмя специальными картами. Основное правило игры следующее: игрок, который выиграл последнюю раздачу, может начать новую с любой допустимой комбинации карт. Далее по очереди каждый игрок может или пропустить, или играть с той же комбинацией карт, но с большими значениями. Процесс продолжается, пока все не спасуют, выигрывает тот, кто предложил последнюю комбинацию карт, он же начинает новую раздачу. Задача игрока - как можно быстрее избавиться от всех имеющихся у него карт.
Основные правила игры дают возможность применить хорошую тактику комбинирования карт таким образом, чтобы сыграть как можно меньшее количество комбинаций. Для простоты рассмотрим здесь более простую версию игры. Проигнорируем специальные карты, таким образом имеем стандартную колоду из 52 карт, значения которых изменяются от 2 до Туза с мастями червы, бубны, кресты и пики. Масти обозначаются прописными буквами h, d, c и s, значения по возрастанию обозначаются символами 2–9, T, J, Q, K, A.
Далее приведен список всех допустимых комбинаций:
одна любая карта;
пара карт одного значения;
три карты одного значения;
четыре карты одного значения;
полный дом, то есть три карты одного значения и две карты другого, но одинакового значения, например 444KK;
стрит длины как минимум пять, то есть пять карт с последовательно возрастающими значениями, например 89TJQK.
Ваша задача - определить наименьшее количество комбинаций, на которое можно разбить имеющиеся у Вас на руках 13 карт.
Входные данные
Первая строка содержит количество тестов, не более 100. Каждый тест содержит:
одну строку, описывающую Ваши 13 карт. Описания карт отделены одним пробелом. Каждая карта описывается двумя символами: значением и мастью. Все карты различные.
Выходные данные
Для каждого теста вывести:
первая строка содержит целое число n: наименьшее количество комбинаций, на которое можно разбить имеющиеся у Вас на руках карты.
n строк, описывающие наименьшее множество комбинаций имеющихся у Вас карт. Каждая строка содержит карты одной допустимой комбинации в формате, как показано в примере. Каждая карта должны встречаться в точности один раз в одной из комбинаций. Порядок вывода комбинаций не важен.