#pragma GCC optimize("O3", "Ofast", "unroll-loops")
// #pragma GCC target("avx", "avx2")
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
const int inf = 1e7;
const pair<int, int> deltas[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
vector<string> a;
vector<vector<int>> vis, dist;
int r, c, mini, minj, maxi, maxj, tt;
vector<pair<int, int>> q;
void dfs(int i, int j) {
q.emplace_back(i, j);
vis[i][j] = tt;
for (const auto& [di, dj] : deltas) {
int newi = i + di, newj = j + dj;
if (newi >= mini && newi <= maxi && newj >= minj && newj <= maxj && vis[newi][newj] < tt && dist[newi][newj] >= dist[i][j]) {
dist[newi][newj] = dist[i][j];
dfs(newi, newj);
}
}
}
void solve() {
int n;
cin >> r >> c >> n;
int sr, sc, gr, gc;
cin >> sr >> sc >> gr >> gc;
--sr, --sc, --gr, --gc;
a.resize(r);
for (int i = 0; i < r; ++i) {
cin >> a[i];
}
vis.resize(r, vector<int>(c, -1));
dist.resize(r, vector<int>(c, inf));
vector<vector<int>> nxt(r, vector<int>(c, -1));
vector<pair<int, int>> ext;
dist[sr][sc] = 0;
q.emplace_back(sr, sc);
tt = -1;
ext.reserve(r * c);
q.reserve(r * c);
while (dist[gr][gc] == inf) {
++tt;
while (!q.empty()) {
auto [i, j] = q.back();
q.pop_back();
if (vis[i][j] == tt) {
continue;
}
vis[i][j] = tt;
ext.emplace_back(i, j);
if ((i - n <= gr && gr <= i + n && j - n + 1 <= gc && gc <= j + n - 1) || (i - n + 1 <= gr && gr <= i + n - 1 && j - n <= gc && gc <= j + n)) {
dist[gr][gc] = min(dist[gr][gc], dist[i][j] + 1);
}
for (const auto& [di, dj] : deltas) {
int newi = i + di, newj = j + dj;
if (newi >= 0 && newi < r && newj >= 0 && newj < c && a[newi][newj] == '.' && dist[newi][newj] > dist[i][j]) {
dist[newi][newj] = dist[i][j];
q.emplace_back(newi, newj);
}
}
}
if (dist[gr][gc] != inf) {
break;
}
for (int iter = 0; iter < 4; ++iter) {
++tt;
sort(ext.begin(), ext.end());
if (iter == 0) {
// up
int lastI = -1, start = -1;
pair<int, int> segj = {0, -1};
bool sameI;
for (auto [i, j] : ext) {
sameI = (lastI == i);
if (lastI == i && segj.second + 1 == j) {
++segj.second;
} else {
for (int k = segj.first; k <= segj.second; ++k) {
nxt[lastI][k] = segj.second + 1;
}
lastI = i, segj = {j, j};
}
mini = max(0, i - n), minj = max(0, j - n + 1);
maxi = min(r - 1, i - 1), maxj = min(c - 1, j + n - 1);
if (i - 1 >= 0) {
int newD = dist[i][j] + 1;
if (sameI) {
j = max(j, start);
}
start = maxj + 1;
--i;
if (j <= maxj && dist[i][j] == newD - 1) {
j = nxt[i][j];
}
if (j <= maxj && dist[i][j] > newD - 1) {
dist[i][j] = newD;
dfs(i, j);
}
}
}
} else if (iter == 1) {
// left
int lastJ = -1, start = -1;
pair<int, int> segi = {0, -1};
bool sameJ;
for (auto [j, i] : ext) {
i = -i;
sameJ = (lastJ == j);
if (lastJ == j && segi.first - 1 == i) {
--segi.first;
} else {
for (int k = segi.first; k <= segi.second; ++k) {
nxt[k][lastJ] = segi.first - 1;
}
lastJ = j, segi = {i, i};
}
mini = max(0, i - n + 1), minj = max(0, j - n);
maxi = min(r - 1, i + n - 1), maxj = min(c - 1, j - 1);
if (j - 1 >= 0) {
int newD = dist[i][j] + 1;
if (sameJ) {
i = min(i, start);
}
start = mini - 1;
--j;
if (i >= mini && dist[i][j] == newD - 1) {
i = nxt[i][j];
}
if (i >= mini && dist[i][j] > newD - 1) {
dist[i][j] = newD;
dfs(i, j);
}
}
}
} else if (iter == 2) {
// down
int lastI = -1, start = -1;
pair<int, int> segj = {0, -1};
bool sameI;
for (auto [i, j] : ext) {
i = -i, j = -j;
sameI = (lastI == i);
if (lastI == i && segj.first - 1 == j) {
--segj.first;
} else {
for (int k = segj.first; k <= segj.second; ++k) {
nxt[lastI][k] = segj.first - 1;
}
lastI = i, segj = {j, j};
}
mini = max(0, i + 1), minj = max(0, j - n + 1);
maxi = min(r - 1, i + n), maxj = min(c - 1, j + n - 1);
if (i + 1 < r) {
int newD = dist[i][j] + 1;
if (sameI) {
j = min(j, start);
}
start = minj - 1;
++i;
if (j >= minj && dist[i][j] == newD - 1) {
j = nxt[i][j];
}
if (j >= minj && dist[i][j] > newD - 1) {
dist[i][j] = newD;
dfs(i, j);
}
}
}
} else {
// right
int lastJ = -1, start = -1;
pair<int, int> segi = {0, -1};
bool sameJ;
for (auto [j, i] : ext) {
j = -j;
sameJ = (lastJ == j);
if (lastJ == j && segi.second + 1 == i) {
++segi.second;
} else {
for (int k = segi.first; k <= segi.second; ++k) {
nxt[k][lastJ] = segi.second + 1;
}
lastJ = j, segi = {i, i};
}
mini = max(0, i - n + 1), minj = max(0, j + 1);
maxi = min(r - 1, i + n - 1), maxj = min(c - 1, j + n);
if (j + 1 < c) {
int newD = dist[i][j] + 1;
if (sameJ) {
i = max(i, start);
}
start = maxi + 1;
++j;
if (i <= maxi && dist[i][j] == newD - 1) {
i = nxt[i][j];
}
if (i <= maxi && dist[i][j] > newD - 1) {
dist[i][j] = newD;
dfs(i, j);
}
}
}
}
for (int i = 0; i < (int)ext.size(); ++i) {
ext[i].first = -ext[i].first;
swap(ext[i].first, ext[i].second);
}
}
ext.clear();
}
cout << dist[gr][gc] << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
int T = 1;
cin >> T;
while (T--) {
solve();
cerr << "-----------\n";
cout << "-----------\n";
}
#else
int T = 1;
// cin >> T;
while (T--) {
solve();
}
#endif
return 0;
}
