Quick out of the Harbour

Interview

Time limit1sMemory limit128 MB

Summary

Find the shortest time from S to outside the grid, where water cells cost 1 and drawbridges cost 1+d, on a grid up to 500x500.

Level: Medium4 of 10
Topics: Graph, Shortest path, Heap, Matrix
Solved: No attempts yet

Problem

Captain Clearbeard went to the harbour for a few days so his crew could inspect and repair the ship. Now, a few days later, the pirates are getting landsick. Before the whole crew becomes too sick to row the ship out, Captain Clearbeard wants to leave the harbour as quickly as possible.

Unfortunately, the harbour is not a straight path to the open sea. To protect the city from evil pirates, the harbour entrance is a maze filled with drawbridges. Every bridge takes some time to open, so a detour may be faster. Your task is to help Captain Clearbeard find the fastest way out to the open sea.

The map is a grid. The pirates row at a speed of one minute per grid cell, and the ship may move only horizontally or vertically (never diagonally). Making a 90-degree turn takes no extra time.

Moving into an adjacent water cell takes 1 minute.
Moving into a drawbridge cell takes $1 + d$ minutes (1 minute to row, plus $d$ minutes to open the bridge).
The open sea is not drawn on the map; it lies just outside the border. Rowing off the edge of the map from a border cell also takes 1 minute.

Note: Pirates get landsick when they don't get enough of the ship's rocking motion. That is why pirates often try to simulate that motion by drinking rum.

Input

The first line contains a single integer: the number of test cases. Each test case has the following format:

One line with three integers $h$ , $w$ ( $3 \le h, w \le 500$ ) and $d$ ( $0 \le d \le 50$ ): the height and width of the map and the delay for opening a bridge.
$h$ $h$ lines of $w$ $w$ characters each, describing the map, using these characters:
- S — the starting position of the ship.
- . — water.
- # — land.
- @ — a drawbridge.

Each harbour is completely surrounded by land, except for a single entrance.

Output

For each test case, print a single line containing one integer: the travelling time of the fastest route to the open sea. A route to the open sea always exists. Remember that the open sea is not shown on the map, so the ship must move off the edge of the map to reach it.

Examples3

Example 1

Input

2
6 5 7
#####
#S..#
#@#.#
#...#
#@###
#.###
4 5 3
#####
#S#.#
#@..#
###@#

Expected output

16
11

Example 2
Input
```
1
3 3 5
###
#S.
###
```
Expected output
```
2
```
Example 3
Input
```
1
3 3 4
###
#S@
###
```
Expected output
```
6
```