#include<bits/stdc++.h>

using namespace std;

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;
short st[N][N][12][12];
int sum[N][N];
int dp[N][N];
char mp[N][N];
int LOG2[N];
int n, m;

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];
}

void init_max_square_len() {
    for (int i = 1; i <= n; ++i) {
        for (int 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;
        }
    }
}

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

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

    for (int k = 1; k <= 11; k++) {
        for (int l = 1; l <= 11; l++) {
            for (int i = 1; i + (1 << k) - 1 <= n; i++) {
                for (int j = 1; j + (1 << l) - 1 <= m; j++) {
                    int x = 1 << k - 1, y = 1 << l - 1;
                    //     i             j
                    st[i][j][k][l] = max({
                        st[i][j][k - 1][l - 1],
                        st[i][j + y][k - 1][l - 1],
                        st[i + x][j][k - 1][l - 1],
                        st[i + x][j + y][k - 1][l - 1]
                    });
                }
            }
        }
    }
}

int query(const int& sx, const int& sy, const int& ex, const int& ey) {
    int k = LOG2[ex - sx + 1], l = LOG2[ey - sy + 1];
    // cout << k << ' ' << l << '\n';
    return max({
        st[sx][sy][k][l],
        st[ex - (1 << k) + 1][sy][k][l],
        st[sx][ey - (1 << l) + 1][k][l],
        st[ex - (1 << k) + 1][ey - (1 << l) + 1][k][l]
    });
}

void solve(const int& x, const 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 (int i = 1; i < N; ++i) LOG2[i] = LOG2[i >> 1] + 1;

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int 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 (int i = 1; i <= q; ++i) {
        int x, y;
        cin >> x >> y;
        solve(x, y);
    }

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