Напрямки#406
У Тентурі не кожен має право носити малинові штани, і далеко не всі володіють пепелацем з гравіцапою, тому для більшості жителів подорож між планетами була складною задачею. Однак заповзятий чатланин із планети Плюк нещодавно з'явився на ринку пасажирських перевезень, пропонуючи поїздки між планетами за кілька чатлів. Подорож починається і закінчується на планеті Плюк, а між цими подіями відвідується кілька інших планет.
Перший рядок вхідних даних містить кількість тестів. У кожному тесті перший рядок містить число (N \leq 22) — кількість планет, які обслуговує маршрут (не рахуючи Плюк). Далі рядків містять інформацію про кожну планету у такому форматі: тип планети (латинська велика літера — чатланська, — пацакська), кількість чатлан, що подорожують на цю планету з Плюка, кількість пацаків, що подорожують на цю планету з Плюка, кількість чатлан, що повертаються з цієї планети на Плюк, та кількість пацаків, що повертаються з цієї планети на Плюк. Загальна кількість пасажирів не перевищує .
Для кожного тесту виведіть мінімальну кількість разів, коли потрібно буде надягати цак на оптимальному маршруті, а далі — порядок відвідування планет через пробіл. Планети, зазначені у вхідних даних, нумеруються з одиниці, планета Плюк має номер і завжди з'являється у послідовності двічі — на початку та наприкінці. Якщо існує кілька оптимальних маршрутів, оберіть той, у якому раніше відвідується планета з меншим номером.
Повний текст задачі дивіться у початковій мові.
Приклад 1