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