3009: 藏宝图

彩虹岛有一个神秘的地方，里面藏着无数的珍宝，这便是朝晖十四号楼。为了找到宝藏，无数勇士不惜踏上了（女装）寻宝的不归路，其中也包括$RoyYuan$。$RoyYuan$在一次偶然中得到了一张藏宝图，已知藏宝图上画着一个$n \times m$的迷宫，其中'$S$' 是迷宫的入口，'$T$'为宝藏的所在地，迷宫中还有很多扇门（在地图上用'\#'表示），所有的门都只会在$k$，$2k$，$3k$ ... 时刻（k的倍数时刻）开启，门只有在开启的时刻可以被经过。$RoyYuan$每次可以在竖直或水平方向移动一步，并且不能选择停留在原地等待（如果无法移动则认为不能到达藏宝地点）。在寻宝的过程中，他也不能走出迷宫边界。由于$RoyYuan$太懒，他不想毫无准备贸然闯入迷宫，他想预先知道他能否通过这个藏宝图走到宝藏所在地，如果可以，最少需要几步才能到达宝藏所在地。

输入第一行为一个整数$T(T \leq 50)$，表示一共有$T$组测试数据。
对于每组测试数据：
第一行为三个整数$n$，$m$，$k$，表示迷宫的大小和门开启的时间$(1 \leq n, m \leq 100, 2 \leq k \leq 10)$。
接下来$n$行每行$m$个字符表示大小为$n \times m$的藏宝图。
其中'$S$'表示起点，'$T$'表示宝藏所在地，'\#'表示门，'$.$'表示无障碍区域。

对于每组测试数据：若能到达宝藏所在地，输出最少的步数$t$；否则输出"-1"（不含引号）。

1
6 6 2
...S..
...#..
.#....
...#..
...#..
..#T#.

7