You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

你的面前有一个巨大的迷宫，迷宫终点摆着一瓶五粮液。

这个迷宫是一个$n\times m$的图，左上角是$(1,1)$，右下角是$(n,m)$。每格上面都有一个字符，分别表示：

S:起点，最初有一个物品在上面。如果起点在$(x,y)$上，物品可以从起点传输到$(x+1,y),(x-1,y),(x,y+1),(x,y-1)$中的任意一点。

T:终点，你的目标是到达这一点。

.:空地，如果物品在空地上面则不能够移动了。

#:中转站，如果中转站在$(x,y)$上，那么下一步你可以从中转站传输到$(x+1,y),(x-1,y),(x,y+1),(x,y-1)$中的任意一点。

^:如果这个格子的坐标为$(x,y)$，那么下一步你就会被传输到$(x-1,y)$。

>:如果这个格子的坐标为$(x,y)$，那么下一步你就会被传输到$(x,y+1)$。

v :如果这个格子的坐标为$(x,y)$，那么下一步你就会被传输到$(x+1,y)$。

<:如果这个格子的坐标为$(x,y)$，那么下一步你就会被传输到$(x,y-1)$。

在上面所有的传输操作中，你不能够被传输到边界外。可以花费$1$块钱将一个传送带的方向顺时针旋转一次，也可以花$p$块钱在一块空地上建设任意一种传送带（新建设的传送带也能够旋转）。

顺时针旋转是指: ^ $\rightarrow$>$\rightarrow$v$\rightarrow$<$\rightarrow$^

你要知道如何花费最少的代价到终点拿到五粮液

输入格式

第一行一个正整数$T(1≤T≤10)$表示测试组数。

接下来T组，每组第一行三个正整数$n,m(2≤n,m≤300),p(1≤p≤100)$表示矩阵的大小和建造传送带的代价。

接下来n行，每行m个字符。字符仅包含题面中描述的几种，并且S和T有且仅有一个。

输出格式

每组输出一个数表示最小花费。

样例 #1

样例输入 #1

3
3 3 10
S..
>..
v>T
3 3 1
S..
>..
v>T
3 3 1
S..
>#.
v>T

样例输出 #1

4
1
0

提示

针对样例1第一组数据，路径为 $(1,1)->(2,1)->(3,1)->(3,2)->(3,3)$ 其中在$(2,1)$点花费1元将传送门方向改变为v，在$(3,1)$点花费三元钱将传送带改为$>$，合计花费为4元。