#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

constexpr int dx[] = {-1, 1, 0, 0};
constexpr int dy[] = {0, 0, -1, 1};

void solve() {
    int N, M, Q;
    std::cin >> N >> M >> Q;
    
    std::vector<std::string> s(N);
    for (int i = 0; i < N; i++) {
        std::cin >> s[i];
    }
    
    int exit = -1;
    
    auto valid = [&](int x, int y) {
        return 0 <= x && x < N && 0 <= y && y < M && s[x][y] != '#';
    };
    auto idx = [&](int x, int y) {
        return x * M + y;
    };
    
    std::vector<std::array<int, 2>> lifts;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (s[i][j] == 'E') {
                exit = idx(i, j);
            }
            if (s[i][j] == '?') {
                lifts.push_back({i, j});
            }
        }
    }
    
    int K = lifts.size();
    std::vector<std::map<int, int>> adj(N * M);
    std::vector<int> deg(N * M);
    for (int mask = 0; mask < (1 << K); mask++) {
        for (int i = 0; i < K; i++) {
            auto [x, y] = lifts[i];
            if (mask >> i & 1) {
                s[x][y] = '#';
            } else {
                s[x][y] = '.';
            }
        }
        
        std::vector dis(N * M, -1);
        std::queue<int> q;
        q.push(exit);
        dis[exit] = 0;
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            
            int x = u / M, y = u % M;
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (valid(nx, ny)) {
                    int v = idx(nx, ny);
                    if (dis[v] == -1) {
                        q.push(v);
                        dis[v] = dis[u] + 1;
                    }
                }
            }
        }
        
        for (int u = 0; u < N * M; u++) {
            if (u == exit) {
                continue;
            }
            int x = u / M, y = u % M;
            if (s[x][y] == '#') {
                continue;
            }
            deg[u]++;;
            if (dis[u] == -1) {
                continue;
            }
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];
                if (valid(nx, ny)) {
                    int v = idx(nx, ny);
                    if (dis[v] == dis[u] - 1) {
                        adj[v][u]++;
                        break;
                    }
                }
            }
        }
    }
    
    std::vector<int> ans(N * M, -1);
    
    std::queue<int> q;
    q.push(exit);
    ans[exit] = 0;
    
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        
        for (auto [u, w] : adj[v]) {
            if ((deg[u] -= w) == 0) {
                q.push(u);
                ans[u] = ans[v] + 1;
            }
        }
    }
    
    for (int i = 0; i < Q; i++) {
        int x, y;
        std::cin >> x >> y;
        x--;
        y--;
        int u = idx(x, y);
        
        std::cout << ans[u] << "\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t;
    std::cin >> t;
    
    for (int i = 1; i <= t; i++) {
        std::cout << "Case " << i << ":\n";
        solve();
    }
    
    return 0;
}