#include<bits/stdc++.h>

using namespace std;

#define RI register int

namespace LJW {
    // TODO quickly read
    inline char getch() { static char buf[1 << 17], *p = buf, *q = buf; return p == q && (q = buf + fread(p = buf, 1, 1 << 17, stdin), p == q) ? EOF : *p++;}
    template<typename T> inline void read(T &x) { x = 0; int f = 0;char ch = getch(); while (ch < '0' || ch > '9') {if (ch == '-') f = 1;ch = getch();} while (ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getch();} if (f) x = (~x) + 1;}
    template<typename T, typename ... Args> inline void read(T &x, Args &... y){ read(x), read(y...); }
    template<typename T, typename F> inline void readn(T a[], F n) { for_each(a + 1, a + n + 1, [](T &x){ read(x); }); }
    // TODO quickly write
    template<typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x < 10) putchar(x ^ 48); else write(x / 10), putchar(x % 10 ^ 48);}
    template<typename T> inline void put(T x, char ch = '\n') { write(x); putchar(ch); }
    template<typename T, typename F> inline void putdec(T x, F num, char ch = '\n') { cout << fixed << setprecision(num) << x << ch; }
    template<typename T, typename F> inline void printn(T a[], F n) { for_each(a + 1, a + n + 1, [](T &x) { put(x, ' '); }); putchar('\n'); }
    // TODO Math
    template<typename T> inline bool chkmax(T &x, T y) { return x < y ? x = y, 1: 0; }
    template<typename T> inline bool chkmin(T &x, T y) { return x > y ? x = y, 1: 0; }
    template<typename T> inline T xaddy(T x, T y){return x ? xaddy((x & y) << 1, x ^ y): y; }
}

using namespace LJW;

const int N = 2e3 + 2;
char mp[N][N];
int sum[N][N];
int dp[N][N];
int st[N][N][12];
int LOG2[N];
int n, m;

inline int calc(int x, int y, int xx, int yy) {
    return sum[xx][yy] - sum[xx][y - 1] - sum[x - 1][yy] + sum[x - 1][y - 1];
}

inline void init_max_square_len() {
    for (RI i = 1; i <= n; ++i) {
        for (RI j = 1; j <= m; ++j) {
            if (mp[i][j] == '#') continue;
            int l = 1, r = min(n - i + 1, m - j + 1);

            while (l <= r) {
                int mid = l + r >> 1;
                int di = i + mid - 1, dj = j + mid - 1;

                if (calc(i, j, di, dj) == mid * mid) l = mid + 1;
                else r = mid - 1;
            }
            dp[i][j] = r;
        }
    }
}

inline void initSt() {
    for (RI i = 1; i <= n; ++i) {
        for (RI j = 1; j <= m; ++j) {
            st[i][j][0] = dp[i][j];
        }
    }

    for (RI i = 1; i <= n; ++i) {
        for (RI k = 1; k <= 11; ++k) {
            for (RI j = 1; j + (1 << k) - 1 <= m; ++j) {
                st[i][j][k] = max(st[i][j][k - 1], st[i][j + (1 << (k - 1))][k - 1]);
            }
        }
    }
}

inline int query(int x, int l, int r) {
    int k = LOG2[r - l + 1];
    return max(st[x][l][k], st[x][r - (1 << k) + 1][k]);
}

inline int query(int sx, int sy, int fx, int fy) {
    int res = 0;
    for (RI i = sx; i <= fx; ++i) {
        res = max(res, query(i, sy, fy));
    }
    return res;
}

inline void solve(int x, int y) {
    if (mp[x][y] == '#') {
        put(0);
        return ;
    }
    int l = 1, r = min(n, m);
    while (l <= r) {
        int mid = l + r >> 1;
        int sx = max(1, x - mid + 1), sy = max(1, y - mid + 1);
        if (query(sx, sy, x, y) >= mid) l = mid + 1;
        else r = mid - 1;
    }
    put(r * r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    LOG2[0] = -1;
    for (RI i = 1; i < N; ++i) LOG2[i] = LOG2[i >> 1] + 1;

    cin >> n >> m;
    for (RI i = 1; i <= n; ++i) {
        for (RI j = 1; j <= m; ++j) {
            cin >> mp[i][j];
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + (mp[i][j] == '.');
        }
    }
    init_max_square_len();
    initSt();
    int q;
    cin >> q;
    for (RI i = 1; i <= q; ++i) {
        int x, y;
        cin >> x >> y;
        solve(x, y);
    }

    // system("pause");
    return 0;
}

T了第32、33、36、37、41-47 的点