Швидко з гавані
Капітан Кларобород вирішив зупинитися в гавані на кілька днів, щоб його команда могла оглянути та полагодити корабель. Однак, через деякий час, пірати почали страждати від "сушеболізні" (це стан, що виникає у піратів, коли вони занадто довго перебувають на суші і їм не вистачає хитавиці корабля. Щоб впоратися з цим, вони часто п'ють ром, намагаючись імітувати рух моря). Щоб уникнути того, що пірати стануть занадто хворими і не зможуть покинути гавань, капітан Кларобород вирішив якнайшвидше вирушити у відкрите море.
На жаль, шлях з гавані не такий простий. Щоб захистити місто від злих піратів, вхід у гавань влаштований як лабіринт з розвідними мостами. Кожен міст вимагає часу на відкриття, тому іноді швидше обійти його. Ваше завдання — допомогти капітану Кларобороду знайти найшвидший шлях до відкритого моря.
Пірати гребуть зі швидкістю одна хвилина на кожен рядок сітки на карті. Корабель може переміщатися тільки горизонтально або вертикально. Поворот на 90 градусів не вимагає додаткового часу.
Вхідні дані
Перший рядок вводу містить одне число: кількість тестів, які потрібно виконати. Кожен тест має наступний формат:
Один рядок з трьома цілими числами: h, w (3 ≤ h; w ≤ 500), і d (0 ≤ d ≤ 50), де h і w — висота і ширина карти, а d — затримка на відкриття мосту.
h рядків по w символів: опис карти. Карта представлена наступними символами:
"S" — початкова позиція корабля.
"." — вода.
"#" — суша.
"@" — розвідний міст.
Кожна гавань повністю оточена сушею, за винятком одного входу.
Вихідні дані
Для кожного тесту у вихідних даних має бути виведено одне ціле число в окремому рядку: час подорожі найшвидшим маршрутом до відкритого моря. Завжди існує маршрут до відкритого моря. Зверніть увагу, що відкрите море не відображено на карті, тому вам потрібно вийти за межі карти, щоб досягти його.