#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#define DEBUG(...) debug(#__VA_ARGS__, __VA_ARGS__)
#else
#define DEBUG(...) 6
#endif

template<typename T, typename S> ostream& operator << (ostream &os, const pair<T, S> &p) {return os << "(" << p.first << ", " << p.second << ")";}
template<typename C, typename T = decay<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr>
ostream& operator << (ostream &os, const C &c) {bool f = true; os << "["; for (const auto &x : c) {if (!f) os << ", "; f = false; os << x;} return os << "]";}
template<typename T> void debug(string s, T x) {cerr << "\033[1;35m" << s << "\033[0;32m = \033[33m" << x << "\033[0m\n";}
template<typename T, typename... Args> void debug(string s, T x, Args... args) {for (int i=0, b=0; i<(int)s.size(); i++) if (s[i] == '(' || s[i] == '{') b++; else
if (s[i] == ')' || s[i] == '}') b--; else if (s[i] == ',' && b == 0) {cerr << "\033[1;35m" << s.substr(0, i) << "\033[0;32m = \033[33m" << x << "\033[31m | "; debug(s.substr(s.find_first_not_of(' ', i + 1)), args...); break;}}

template<typename T>
struct BIT {
    int n, lg;
    vector<T> bit;

    BIT(int _n) : n(_n), lg(__lg(n)), bit(n + 1) {}

    BIT(const vector<T> &a) : n((int) a.size()), lg(__lg(n)), bit(n + 1) {
        for (int i=1; i<=n; i++) {
            bit[i] += a[i-1];
            if (i + (i & -i) <= n)
                bit[i+(i&-i)] += bit[i];
        }
    }

    T query(int i) {
        T ret = 0;
        for (; i>0; i-=i&-i)
            ret += bit[i];
        return ret;
    }

    T query(int l, int r) {
        return query(r) - query(l-1);
    }

    void update(int i, T val) {
        for (; i<=n; i+=i&-i)
            bit[i] += val;
    }

    int kth(T k) {
        int ret = 0;
        for (int i=lg; i>=0; i--) {
            ret += 1 << i;
            if (ret <= n && bit[ret] < k)
                k -= bit[ret];
            else
                ret -= 1 << i;
        }
        return ret + 1;
    }
};

struct SegmentTree {
    int n;
    vector<int> a, st, lazy;

    SegmentTree(int _n) : n(_n), st(4*n), lazy(4*n) {}

    SegmentTree(const vector<int> &_a) : n((int) _a.size()), a(_a), st(4*n), lazy(4*n) {
        build(1, 0, n-1);
    }

    void build(int p, int l, int r) {
        if (l == r) {
            st[p] += a[l];
            return;
        }
        int m = (l + r) / 2;
        build(2*p, l, m);
        build(2*p+1, m+1, r);
        st[p] = min(st[2*p], st[2*p+1]);
    }

    void push(int p, int l, int r) {
        if (lazy[p]) {
            st[p] += lazy[p];
            if (l != r) {
                lazy[2*p] += lazy[p];
                lazy[2*p+1] += lazy[p];
            }
            lazy[p] = 0;
        }
    }

    int query(int p, int l, int r, int i, int j) {
        push(p, l, r);
        if (i > r || j < l)
            return INT_MAX;
        if (i <= l && r <= j)
            return st[p];
        int m = (l + r) / 2;
        return min(query(2*p, l, m, i, j), query(2*p+1, m+1, r, i, j));
    }

    int query(int i, int j) {
        return query(1, 0, n-1, i, j);
    }

    void update(int p, int l, int r, int i, int j, int val) {
        push(p, l, r);
        if (i > r || j < l)
            return;
        if (i <= l && r <= j) {
            st[p] += val;
            if (l != r) {
                lazy[2*p] += val;
                lazy[2*p+1] += val;
            }
            return;
        }
        int m = (l + r) / 2;
        update(2*p, l, m, i, j, val);
        update(2*p+1, m+1, r, i, j, val);
        st[p] = min(st[2*p], st[2*p+1]);
    }

    void update(int i, int j, int val) {
        update(1, 0, n-1, i, j, val);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int cn=1; cn<=t; cn++) {
        int r, c, k, q;
        cin >> r >> c >> k >> q;
        k--;
        vector<string> g(r);
        vector<BIT<int>> bit(c, BIT<int>(r));
        vector<set<int>> st(c);
        for (int i=0; i<r; i++) {
            cin >> g[i];
            for (int j=0; j<c; j++)
                if (g[i][j] == 'X') {
                    bit[j].update(i + 1, 1);
                    st[j].insert(i);
                }
        }
        vector<pair<int, int>> queries;
        for (int i=0; i<q; i++) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            queries.emplace_back(a, b);
        }

        // 0-based to 1-based
        auto upd = [&] (int j, int i, int x) -> void {
            bit[j].update(i + 1, x);
        };

        auto query = [&] (int j, int l, int r) -> int {
            return bit[j].query(l + 1, r + 1);
        };

        auto shiz = [&] (int i) -> int {
            return max(k - i, -1);
        };

        // down shifts (use upper row)
        // find clog point
        // shift 0, 1, 2, ..., r times (might be r - 1 but whatever)
        // if it's clogged at shift s, then all later shifts are guaranteed to have a car there
        SegmentTree stDown(r + 1);
        vector<int> cnt(c), clog(c, -1);
        int tot = 0;
        for (int j=0; j<c; j++) {
            cnt[j] = query(j, k, r - 1);
            if (cnt[j] == r - k)
                clog[j] = 0;
            tot += g[k][j] == 'X';
        }
        // DEBUG("INIT", cn, cnt);
        stDown.update(0, 0, tot);
        for (int s=1; s<=r; s++) {
            int tot = s;
            for (int j=0; j<c; j++) {
                bool car = k - s >= 0 ? g[k-s][j] == 'X' : false;
                if (clog[j] == -1) {
                    // shift one above
                    if (car) {
                        cnt[j]++;
                        if (cnt[j] == r - k)
                            clog[j] = s;
                    }
                }
                tot += car || clog[j] != -1;
            }
            stDown.update(s, s, tot);
        }
        // DEBUG(cn, clog);

        // do the updates for the down shifts
        vector<int> ret(q, INT_MAX);
        vector<string> old = g;
        for (int i=0; i<q; i++) {
            auto [a, b] = queries[i];
            int yyyy = shiz(a);
            if (g[a][b] == 'X') {
                // remove car
                // clog point could move up
                g[a][b] = '.';
                st[b].erase(a);
                upd(b, a, -1);
                if (clog[b] != -1 && yyyy <= clog[b]) {
                    // DEBUG("REM", cn, a, b, clog[b], st[b]);
                    if (cn == 6) DEBUG(yyyy);
                    if (yyyy != -1) stDown.update(yyyy, yyyy, -1);
                    stDown.update(clog[b] + 1, r, -1);
                    auto it = st[b].lower_bound(k - clog[b]);
                    if (it == st[b].begin()) {
                        // no clog point
                        clog[b] = -1;
                    } else {
                        // yes clog point
                        clog[b] = shiz(*prev(it));
                        stDown.update(clog[b], r, 1);
                    }
                    // DEBUG(clog[b]);
                } else if (clog[b] == -1) {
                    if (yyyy != -1) stDown.update(yyyy, yyyy, -1);
                }
            } else {
                // insert car
                // clog point could move down
                g[a][b] = 'X';
                st[b].insert(a);
                upd(b, a, 1);
                if (clog[b] != -1 && yyyy < clog[b]) {
                    // DEBUG("INS", cn, a, b, clog[b]);
                    if (yyyy != -1) stDown.update(yyyy, yyyy, 1);
                    stDown.update(clog[b], r, -1);
                    auto it = next(st[b].find(k - clog[b]));
                    // yes clog point
                    clog[b] = shiz(*it);
                    stDown.update(clog[b] + 1, r, 1);
                } else if (clog[b] == -1 && (int) st[b].size() >= r - k) {
                    // DEBUG("PP?");
                    int pp = bit[b].kth((int) st[b].size() - (r - k) + 1) - 1;
                    DEBUG(i, pp);
                    int cnt = query(b, pp, r - 1);
                    DEBUG(cnt);
                    if (cnt == r - k) {
                        // clog point
                        clog[b] = shiz(pp);
                        stDown.update(clog[b] + (clog[b] != yyyy), r, 1);
                        DEBUG(clog[b]);
                        if (yyyy < clog[b] && yyyy != -1) stDown.update(yyyy, yyyy, 1);
                    }
                } else if (clog[b] == -1) {
                    if (yyyy != -1) stDown.update(yyyy, yyyy, 1);
                }
            }
            if (cn == 6) DEBUG(cn, i, a, b, st[b], clog);
            // DEBUG(stDown.query(0, r));
            // for (int i=0; i<=r; i++)
            //     DEBUG(i, stDown.query(i, i));
            ret[i] = min(ret[i], stDown.query(0, r));
        }

        // holy fuck do the same thing with up shift kill me please
        // check rows below
        {
            vector<BIT<int>> bit(c, BIT<int>(r));
            vector<set<int>> st(c);
            g = old;
            for (int i=0; i<r; i++) {
                // cin >> g[i];
                for (int j=0; j<c; j++)
                    if (g[i][j] == 'X') {
                        bit[j].update(i + 1, 1);
                        st[j].insert(i);
                    }
            }

            // 0-based to 1-based
        auto upd = [&] (int j, int i, int x) -> void {
            bit[j].update(i + 1, x);
        };

        auto query = [&] (int j, int l, int r) -> int {
            return bit[j].query(l + 1, r + 1);
        };

            auto blah = [&] (int i) -> int {
                return max(i - k, -1);
            };

            SegmentTree stDown(r + 1);
            vector<int> cnt(c), clog(c, -1);
            int tot = 0;
            for (int j=0; j<c; j++) {
                cnt[j] = query(j, 0, k);
                if (cnt[j] == k + 1)
                    clog[j] = 0;
                tot += g[k][j] == 'X';
            }
            // DEBUG("INIT", cn, cnt);
            stDown.update(0, 0, tot);
            for (int s=1; s<=r; s++) {
                int tot = s;
                for (int j=0; j<c; j++) {
                    bool car = k + s < r ? g[k+s][j] == 'X' : false;
                    if (clog[j] == -1) {
                        // shift one above
                        if (car) {
                            cnt[j]++;
                            if (cnt[j] == k + 1)
                                clog[j] = s;
                        }
                    }
                    tot += car || clog[j] != -1;
                }
                stDown.update(s, s, tot);
            }
            if (cn == 5) DEBUG(cn, clog);

            // do the updates for the up shifts
            for (int i=0; i<q; i++) {
                auto [a, b] = queries[i];
                int yyyy = blah(a);
                if (g[a][b] == 'X') {
                    // remove car
                    // clog point could move down
                    g[a][b] = '.';
                    st[b].erase(a);
                    upd(b, a, -1);
                    if (clog[b] != -1 && yyyy <= clog[b]) {
                        if (cn == 5) DEBUG("REM", cn, a, b, yyyy, clog[b], st[b]);
                        if (yyyy != -1) stDown.update(yyyy, yyyy, -1);
                        stDown.update(clog[b] + 1, r, -1);
                        auto it = st[b].upper_bound(k + clog[b]);
                        if (cn == 5) DEBUG(st[b]);
                        if (it == st[b].end()) {
                            // no clog point
                            if (cn == 5) DEBUG("NONONO");
                            clog[b] = -1;
                        } else {
                            // yes clog point
                            clog[b] = blah(*(it));
                            stDown.update(clog[b], r, 1);
                        }
                        // DEBUG(clog[b]);
                    } else if (clog[b] == -1) {
                        if (yyyy != -1) stDown.update(yyyy, yyyy, -1);
                    }
                } else {
                    // insert car
                    // clog point could move down
                    g[a][b] = 'X';
                    st[b].insert(a);
                    upd(b, a, 1);
                    DEBUG("HEY", yyyy);
                    if (clog[b] != -1 && yyyy < clog[b]) {
                        // DEBUG("INS", cn, a, b, clog[b]);
                        if (yyyy != -1) stDown.update(yyyy, yyyy, 1);
                        stDown.update(clog[b], r, -1);
                        auto it = prev(st[b].find(k + clog[b]));
                        // yes clog point
                        clog[b] = blah(*it);
                        stDown.update(clog[b] + 1, r, 1);
                    } else if (clog[b] == -1 && (int) st[b].size() >= k + 1) {
                        DEBUG(i, "PP?");
                        int pp = bit[b].kth(k + 1) - 1;
                        // DEBUG(pp, r, k + 1, st[b].size(), st[b]);
                        // for (int j=0; j<r; j++)
                        //     DEBUG(bit[j].query(j + 1, j + 1));
                        int cnt = query(b, 0, pp);
                        // DEBUG(cnt);
                        if (cnt == k + 1) {
                            // clog point
                            clog[b] = blah(pp);
                            stDown.update(clog[b] + (clog[b] != yyyy), r, 1);
                            DEBUG(clog[b]);
                            DEBUG(stDown.query(0, 0));
                            if (yyyy < clog[b] && yyyy != -1) stDown.update(yyyy, yyyy, 1);
                        }
                    } else if (clog[b] == -1) {
                        if (yyyy != -1) stDown.update(yyyy, yyyy, 1);
                    }
                }
                // DEBUG(cn, i, a, b, st[b], clog[b]);
                DEBUG(i, stDown.query(0, r));
                    for (int i=0; i<=r; i++)
                        DEBUG(i, stDown.query(i, i));
                DEBUG(clog);
                ret[i] = min(ret[i], stDown.query(0, r));
            }
        }

        DEBUG(cn, ret);
        cout << "Case #" << cn << ": " << accumulate(ret.begin(), ret.end(), 0LL) << "\n";
    }

    return 0;
}