Від сутінків до світанку#6227

Від сутінків до світанку

1 секунда

64 мегабайти

Легка

Володимир має білу шкіру, дуже довгі зуби і йому $600$ років, але це не проблема, адже Володимир — вампір. У Володимира ніколи не було проблем з тим, що він вампір. Насправді, він дуже успішний лікар, який завжди бере нічні зміни, тому має багато друзів серед своїх колег. У нього є вражаючий трюк, який він показує на вечірках: він може визначити групу крові на смак.

Володимир любить подорожувати, але, будучи вампіром, він має подолати три проблеми.

По-перше, він може подорожувати тільки поїздом, оскільки йому потрібно брати з собою свою труну. (З іншого боку, він завжди може подорожувати першим класом, адже вклав багато грошей у довгострокові акції.)
По-друге, він може подорожувати лише від сутінків до світанку, тобто з $18$ години до $6$ години. Протягом дня він має залишатися всередині вокзалу. По-третє, він має взяти з собою щось поїсти. Йому потрібен один літр крові на день, який він випиває опівдні ( $12$ : $00$ ) всередині своєї труни.

Ви повинні допомогти Володимиру знайти найкоротший маршрут між двома заданими містами, щоб він міг подорожувати з мінімальною кількістю крові. (Якщо він візьме занадто багато з собою, люди будуть ставити дивні запитання на кшталт "Що ви робите з усією цією кров'ю?")

Вхідні дані

Перший рядок вхідних даних міститиме одне число, яке вказує кількість тестових випадків. Кожна специфікація тестового випадку починається з одного числа, яке вказує, скільки специфікацій маршрутів слідує. Кожна специфікація маршруту складається з назв двох міст, часу відправлення з першого міста та загального часу подорожі. Часи вказані в годинах.

Зверніть увагу, що Володимир не може використовувати маршрути, які відправляються раніше $18$ : $00$ або прибувають пізніше $6$ : $00$ . Буде не більше $100$ міст і менше $1000$ з'єднань. Жоден маршрут не займає менше однієї години і більше $24$ годин. (Зверніть увагу, що Володимир може використовувати тільки маршрути з максимальною тривалістю подорожі $12$ годин (від сутінків до світанку).) Усі назви міст коротші за $32$ символи.

Останній рядок містить назви двох міст. Перше — місто відправлення Володимира, друге — місто призначення Володимира.

Вихідні дані

Для кожного тестового випадку ви повинні вивести номер тестового випадку, після якого

Володимиру потрібно # літр(ів) крові.

або

Немає маршруту, яким Володимир може скористатися.

Приклади

Приклад 1