// Subtasks:
// 1: AC
// 2: AC
// _: TLE

#include <iostream>
#include <vector>

using namespace std;

#define N 1000
#define K 20
#define Q 200000

int n, q;
string grid[N+1];

int count = 0;
int block_x[N*N+1];
int min_y[N*N+1], max_y[N*N+1];
int what[N+1][N+1];

vector<int> tree[N*N+1];

int answer[Q+1];
vector<vector<int>> queries[N+1][N+1];

int dist[N+1][N+1];
int seen[N+1][N+1];
int start[N+1][N+1];

int done[N*N+1];

int rc = 0;
void process_root(int r) {
    rc++;
    int x = block_x[r];
    vector<pair<int,int>> queue;
    for (int y = min_y[r]; y <= max_y[r]; y++) {
        dist[y][x] = 0;
        seen[y][x] = rc;
        start[y][x] = y;
        queue.push_back({y,x});
    }
    int dy[4] = {0, 0, 1, -1};
    int dx[4] = {1, -1, 0, 0};
    for (int i = 0; i < queue.size(); i++) {
        int cy = queue[i].first;
        int cx = queue[i].second;
        for (int j = 0; j < 4; j++) {
            int uy = cy + dy[j];
            int ux = cx + dx[j];
            if (grid[uy][ux] == '#' && seen[uy][ux] != rc && !done[what[uy][ux]]) {
                seen[uy][ux] = rc;
                start[uy][ux] = start[cy][cx];
                dist[uy][ux] = dist[cy][cx] + 1;
                queue.push_back({uy, ux});
                for (auto v : queries[uy][ux]) {
                    int qy = v[0];
                    int qx = v[1];
                    int qi = v[2];
                    if (seen[qy][qx] == rc) {
                        int d = dist[qy][qx] + dist[uy][ux] +
                                abs(start[qy][qx] - start[uy][ux]);
                        answer[qi] = min(answer[qi], d);
                    }
                }
            }
        }
    }
    done[r] = 1;
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        cin >> grid[i];
        grid[i] = '.' + grid[i];
    }

    int other = 0;
    for (int x = 1; x <= n; x++) {
        for (int y = 1; y <= n; y++) {
            if (grid[y][x] == '#') {
                if (grid[y-1][x] == '.') {
                    count++;
                    block_x[count] = x;
                    min_y[count] = y;
                }
                max_y[count] = y;
                what[y][x] = count;
                if (what[y][x-1] && other != what[y][x-1]) {
                    other = what[y][x-1];
                    tree[other].push_back(count);
                    tree[count].push_back(other);
                }
            } else {
                other = 0;
            }
        }
    }

    for (int i = 1; i <= q; i++) {
        int y1, x1, y2, x2;
        cin >> y1 >> x1 >> y2 >> x2;
        queries[y1][x1].push_back({y2, x2, i});
        queries[y2][x2].push_back({y1, x1, i});
        if (what[y1][x1] == what[y2][x2]) {
            answer[i] = abs(y1 - y2);
        } else {
            answer[i] = 1e9;
        }
    }

    vector<pair<int,int>> ranges;
    ranges.push_back({1,count});
    for (int i = 0; i < ranges.size(); i++) {
        int root = (ranges[i].first + ranges[i].second) / 2;
        process_root(root);
        if (root - 1 >= ranges[i].first) {
            ranges.push_back({ranges[i].first, root - 1});
        }
        if (root + 1 <= ranges[i].second) {
            ranges.push_back({root + 1, ranges[i].second});
        }
    }

    for (int i = 1; i <= q; i++) {
        cout << answer[i] << "\n";
    }
}
