#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <vector>#include <cctype>#include <algorithm>using namespace std;int sx, sy, ex, ey;int N, M, K, H;struct monsters { int hp, x, y, step; int dir, fz, po; void init() { hp = H, x = sx, y = sy, step = 0; fz = po = 0, dir = -1; }};struct tower { int id, x, y; int obj; void init(int Id, int X, int Y) { id = Id, x = X, y = Y, obj = -1; }};int dir[4][2] = {0,1,0,-1,-1,0,1,0};int ff[8][2] = {0,1,0,-1,-1,0,1,0,1,1,1,-1,-1,1,-1,-1};char mp[55][55];monsters m[55];tower t[55][55];bool legal(int x, int y) { if (x < 1 || x > N || y < 1 || y > M) return false; return true;}int cmp(int a, int b) { if (a == -1) return b; if (b == -1) return a; if (m[a].step != m[b].step) { if (m[a].step > m[b].step) { return a; } else return b; } else { if (a < b) { return a; } else return b; }}bool over(int x) { if (x < K) return false; for (int i = 1; i <= x; ++i) { if (m[i].hp > 0) return false; } return true;}void solve() { int many = 0, ti; bool fail = false; for (ti = 1; !over(many) && !fail; ++ti) { bool change = false; for (int i = 1; i <= many; ++i) { if (m[i].hp <= 0) continue; if (m[i].po) { m[i].hp -= 10; change = true; if (m[i].hp <= 0) { continue; } } if (m[i].fz) { m[i].fz = 0; } else { m[i].step += 1; change = true; for (int j = 0; j < 4; ++j) { if (j == m[i].dir) continue; int cx = m[i].x + dir[j][0], cy = m[i].y + dir[j][1]; if (legal(cx, cy) && (mp[cx][cy] == '.' || mp[cx][cy] == 'T')) { m[i].x = cx, m[i].y = cy, m[i].dir = j ^ 1; break; } } if (m[i].x == ex && m[i].y == ey) { fail = true; break; } } } if (fail) continue; if (ti <= K) { m[ti].init(); change = true; } many = min(ti, K); for (int i = 1; i <= many; ++i) { if (m[i].hp <= 0) continue; for (int j = 0; j < 8; ++j) { int cx = m[i].x + ff[j][0], cy = m[i].y + ff[j][1]; if (legal(cx, cy) && isdigit(mp[cx][cy])) { if (t[cx][cy].id != 2) { t[cx][cy].obj = cmp(t[cx][cy].obj, i); } else { m[i].hp -= 10; change = true; } } } } for (int i = 1; i <= N; ++i) { for (int j = 1; j <= M; ++j) { if (t[i][j].id && t[i][j].id != 2 && t[i][j].obj != -1) { if (t[i][j].id == 1) { change = true; m[t[i][j].obj].hp -= 10; } else if (t[i][j].id == 3) { change = true; m[t[i][j].obj].po = 1; } else { m[t[i][j].obj].fz = 1; } t[i][j].obj = -1; } } } if (!change) fail = true; } if (fail) puts("-1"); else printf("%dn", ti - 1);}int main() { int T; for (scanf("%d", &T); T; --T) { scanf("%d %d %d %d", &N, &M, &K, &H); for (int i = 1; i <= N; ++i) { scanf("%s", mp[i]+1); for (int j = 1; j <= M; ++j) { t[i][j].id = 0; if (mp[i][j] == 'X' || mp[i][j] == '.') continue; else if (mp[i][j] == 'B') mp[i][j] = '1', t[i][j].init(1, i, j); else if (mp[i][j] == 'F') mp[i][j] = '2', t[i][j].init(2, i, j); else if (mp[i][j] == 'N') mp[i][j] = '3', t[i][j].init(3, i, j); else if (mp[i][j] == 'I') mp[i][j] = '4', t[i][j].init(4, i, j); else if (mp[i][j] == 'S') sx = i, sy = j; else ex = i, ey = j; } } solve(); } return 0; }
