// https://szkopul.edu.pl/problemset/problem/E0WdV0P4l3hYG2WAuFWyQ-TV/site/?key=statement

#include <bits/stdc++.h>

using namespace std;

constexpr int sizik = 1511;

#define ar std::array
#define pr std::pair
#define vec std::vector

typedef long long ll;
typedef vec<vec<int>> _kra;

struct B {
    int pos, cnt;
    B(int pos1 = 0, int cnt1 = 0) {
        pos = pos1;
        cnt = cnt1;
    }
};

template<typename T>
struct DrzewoPrzedzialoweNaPrzedziale {
    T d[4 * sizik];
    int ll = 1;

    T op(const T& a, const T& b) { return std::max(a, b); }

    T na_przedziale(int o, int x, int y, int A, int B) {
        if (A <= x && y <= B) {
            return d[o];
        } else if (B < x || y < A) {
            // return neutral_element;
            return 0;
        } else {
            return op(na_przedziale(o * 2, x, (x + y) / 2, A, B), na_przedziale(o * 2 + 1, (x + y) / 2 + 1, y, A, B));
        }
    }

    T na_przedziale(int A, int B) { return na_przedziale(1, 1, ll, A, B); }

    void akt(int v, const T& a) {
        v += this->ll - 1;
        d[v] = a;
        while (v > 1) {
            v /= 2;
            d[v] = op(d[2 * v], d[2 * v + 1]);
        }
    }

    DrzewoPrzedzialoweNaPrzedziale(int n = sizik) {
        while (ll < n) {
            ll *= 2;
        }
    }
};

template<typename T>
struct DrzewoPrzedzialowe {
    T d[4 * sizik];
    int ll = 1;

    T op(const T& a, const T& b) { return std::max(a, b); }

    void akt(int o, int x, int y, int A, int B, const T& a) {
        if (A <= x && y <= B) {
            d[o] = op(d[o], a);
            return;
        }
        if (B < x || y < A) return;
        akt(2 * o, x, (x + y) / 2, A, B, a);
        akt(2 * o + 1, (x + y) / 2 + 1, y, A, B, a);
    }

    void akt(int A, int B, const T& a) {
        if (A <= B) akt(1, 1, ll, A, B, a);
    }

    T w_punkcie(int v) {
        v += ll - 1;
        T res = 0;
        while (v > 0) {
            res = op(res, d[v]);
            v /= 2;
        }

        return res;
    }

    DrzewoPrzedzialowe(int n) {
        while (ll < n) {
            ll *= 2;
        }
    }
};

int col[sizik], row[sizik];
char mapa[sizik][sizik], mapa_temp[sizik][sizik];

std::array<std::array<B, 3>, sizik> best_row, best_col;
int n;
DrzewoPrzedzialowe<int> max_c(sizik), max_r(sizik);
DrzewoPrzedzialoweNaPrzedziale<int> max_c1[sizik], max_r1[sizik];
int ans = 0;
std::vector<int> tmp1, tmp2;

void gen(), gen_row(), gen_col(), dbg1();

void solve() {
    int m;
    std::cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            std::cin >> mapa[i][j];
            mapa_temp[i][j] = mapa[i][j];
        }
    }
    gen();
    if (m == 1) {
        int ans1 = 0;
        for (int i = 1; i <= n; i++) {
            ans1 = std::max({ans1, best_col[i][0].cnt, best_row[i][0].cnt});
        }

        std::cout << ans1 << '\n';

        return;
    }
    for (int i = 1; i <= n; i++) {
        int local_tmp = max_r.w_punkcie(i);

        for (int j = 0; j < best_col[i].size(); j++) {
            const auto& alfa = best_col[i][j];

            int local_tmp2 = std::max(max_c1[i].na_przedziale(1, alfa.pos - 1), max_c1[i].na_przedziale(alfa.pos + alfa.cnt, n));

            for (int k = alfa.cnt; k >= 1; k--) {
                int q = alfa.cnt - k;

                int local_tmp3 = std::max(max_c1[i].na_przedziale(alfa.pos, alfa.pos + q - 1),
                                          max_c1[i].na_przedziale(alfa.pos + alfa.cnt - q, alfa.pos + alfa.cnt - 1));

                ans = std::max(ans, std::min(k, std::max({local_tmp, local_tmp2, local_tmp3})));
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        int local_tmp = max_c.w_punkcie(i);

        for (int j = 0; j < best_row[i].size(); j++) {
            const auto& alfa = best_row[i][j];

            int local_tmp2 = std::max(max_r1[i].na_przedziale(1, alfa.pos - 1), max_r1[i].na_przedziale(alfa.pos + alfa.cnt, n));

            for (int k = alfa.cnt; k >= 1; k--) {
                int q = alfa.cnt - k;

                int local_tmp3 = std::max(max_r1[i].na_przedziale(alfa.pos, alfa.pos + q - 1),
                                          max_r1[i].na_przedziale(alfa.pos + alfa.cnt - q, alfa.pos + alfa.cnt - 1));

                ans = std::max(ans, std::min(k, std::max({local_tmp, local_tmp2, local_tmp3})));
            }
        }
    }

    std::cout << ans << '\n';
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;

    for (; t > 0; t--) {
        solve();
    }

    return 0;
}

void gen_row() {
    for (int i = 1; i <= n; i++) {
        int prev = 0;
        std::vector<B> av{0};
        for (int j = 1; j <= n + 1; j++) {
            if (mapa[i][j] == '.') {
                prev++;
            } else {
                av.push_back({j - prev, prev});
                prev = 0;
            }
        }

        std::sort(av.begin(), av.end(), [](const auto& a, const auto& b) { return std::greater<int>()(a.cnt, b.cnt); });

        for (int k = 0; k < (int)best_row[i].size(); k++) {
            best_row[i][k] = av[k];
            tmp1.push_back(av[k].cnt);
        }

        for (const auto& b : av) {
            max_r.akt(1, b.pos - 1, b.cnt);
            max_r.akt(b.pos + b.cnt, n, b.cnt);

            for (int z = b.pos; z < b.pos + b.cnt; z++) {
                max_c1[z].akt(i, b.cnt);
            }
        }
    }
}

void gen_col() {
    for (int j = 1; j <= n; j++) {
        int prev = 0;
        std::vector<B> av{0};
        for (int i = 1; i <= n + 1; i++) {
            if (mapa[i][j] == '.') {
                prev++;
            } else {
                av.push_back({i - prev, prev});
                prev = 0;
            }
        }

        std::sort(av.begin(), av.end(), [](const auto& a, const auto& b) { return std::greater<int>()(a.cnt, b.cnt); });

        for (int k = 0; k < (int)best_col[j].size(); k++) {
            best_col[j][k] = av[k];
            tmp2.push_back(av[k].cnt);
        }

        for (const auto& b : av) {
            max_c.akt(1, b.pos - 1, b.cnt);
            max_c.akt(b.pos + b.cnt, n, b.cnt);

            for (int z = b.pos; z < b.pos + b.cnt; z++) {
                max_r1[z].akt(j, b.cnt);
            }
        }
    }
}

void gen() {
    gen_row();
    gen_col();

    std::sort(tmp1.begin(), tmp1.end(), std::greater<int>());
    std::sort(tmp2.begin(), tmp2.end(), std::greater<int>());
    ans = std::max({ans, tmp1[0] / 2, tmp1[1], tmp2[0] / 2, tmp2[1]});
}

void dbg1() {
    std::cout << "START -~ BEST_ROW[sm]\n";
    for (int cnt = 1; cnt <= n; cnt++) {
        const auto& arr = best_row[cnt];
        std::cout << cnt << "\n";
        for (const auto& g : arr) {
            std::cout << g.cnt << " " << g.pos << '\n';
        }
        std::cout << '\n';
    }
    std::cout << "START -~ BEST_COL[sm]\n";
    for (int cnt = 1; cnt <= n; cnt++) {
        const auto& arr = best_col[cnt];
        std::cout << cnt << "\n";
        for (const auto& g : arr) {
            std::cout << g.cnt << " " << g.pos << '\n';
        }
        std::cout << '\n';
    }
}