Далеко не всі у Тентурі мають право носити малинові штани, і звичайно, не всі воладіють пепелацем з гравіцапою, тому для більшості жителів проблема пересування між планетами була нерозв`язуваною. Але з деяких пір один запопадливий чатланин з планети Плюк вийшов на ринок пасажирських перевезень, і за небагато чатлів, готовий перевозити бажаючих з планети на планету. Рейс починається з планети Плюк, включає декілька інших планет, і завершується там же, на планеті Плюк. Однак при підготовці рейсу виникли несподівані проблеми. Наприклад, якщо чатланин с планети Плюк хоче попасти на планету, яка є в рейсі передостанньою -- йому мимоволі прийдеться відвідати всі планети, які знаходяться в рейсі між планетою Плюк і його точкою призначення. Очевидно, що частина планет у цьому списку можуть виявитись пацакськими. Але кожен чатланин зобов`язаний носити цак на пацакській планеті і, навпаки, кожен пацак повинен носити цак на чатланській планеті. (Цак --- дзвоник для носа, знак відмінності для відносно нижчої касти на даній планеті). А процедура носіння цака принизлива у любому змісті цього слова… \includegraphics{https://static.e-olymp.com/content/59/593bd271f6261d2811fca3add05fddead85ad98d.jpg} Оскільки дане бюро пудорожей поки ще не має представництв на інших планетах, перевезення здійснюється лише з планети Плюк на якусь іншу, або з іншої планети на Плюк. Задача планування рейсу спрощується -- можна відвідувати планети у довільному порядку (але не можна відвідувати одну й ту ж планету двічі -- на шляху може закінчитись луц). Необхідно знайти такий порядок відвідування планет, при якому надівати цак на проміжних планетах доведеться мінімальну кількість разів. \InputFile Перший рядок входу містить кількість тестів. Перший рядок кожного тесту містить число \textbf{N }≤\textbf{ 22} -- кількість планет, що обслуговуються даним рейсом (не рахуючи планети Плюк). \textbf{N} наступних рядків містять інформацію про планети у наступному вигляді: тип планети (латинська велика літера \textbf{С} -- чатланська, \textbf{P} -- пацакська), кількість чатлан, що переміщуються до цієї планети з Плюка, кількість пацаків, що переміщуються до цієї планети з Плюка, кількість чатлан, що переміщуються з даної планети на Плюк, кількість пацаків,що переміщуються з даної планети на Плюк. Всьго пасажирів ≤ \textbf{1000}. \OutputFile Для кожного тесту у вихідний файл виводиться, скільки разів прийдеться надівати цак при оптимальномц маршруті, потім порядок відвідування планет через пропуск. Планети, перераховані у вхідному файлі, нумеруються починаючи з одиниці, планета Плюк має номер нуль і завжди вказується у послідовності двічі -- на початку і в кінці послідовності. Якщо існує декілька оптимальних маршрутів -- вибираиь той, де планета з меншим номером відвідується раніше. \textbf{Коментарі до прикладу}: у першому рейсі можливі два варіанти маршруту: \textbf{0} \textbf{1} \textbf{2} \textbf{0}, та \textbf{0} \textbf{2} \textbf{1} \textbf{0}. У першому варіанті при посадці на чатланській планеті \textbf{1} п`ятьом пацакам, які слідують транзитом до своєї планети \textbf{2}, прийдеться надіти цак, а при наступній посадці на пацакській планеті \textbf{2}, п`ятьом чатланинам, які сіли на планеті \textbf{1} і слідуютю до Плюка, також прийдеться надіти цак. Всього у першому варіанті маршруту цак надівається \textbf{10} разів. У варіанті \textbf{2} цак на проміжних посадках надівається \textbf{4} та \textbf{1} раз відповідно, всьоо \textbf{5} разів. Другий варіант кращий. У другому рейсі всі планети чатланські, тому надівати цак прийдетья лише пацакам. З Плюка пацаки не відправляються, але прибувають з трьох різних планет по одному. Першою відвідується єдина планета, де пацак не заходить в пепелац, потім йде три планети з однаковим набором пасажирів -- на другому кроці з трьох рівноцінних планет, що залишилися, вибирається планета номер \textbf{2} як така, що має найменший номер, потім \textbf{3} і останняя \textbf{4}. Пасажир с останньої планети не має проміжних посадок, передостанньої здійснює одну посадку і надіває цак \textbf{1} раз, і пассажир, що залишився, надіває цак на двох проміжних зупинках, всього цак надівається \textbf{3} рази.