#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = (1<<30)-1;
const ll INF = (1LL<<60)-1;
const ld EPS = 1e-10;
template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};
template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};

int main(){
    int H, W;
    cin >> H >> W;
    string S[H];
    rep(i, H) cin >> S[i];

    int cnt[H+1][W+1];
    rep(i, H+1) cnt[i][0] = 0;
    rep(j, W+1) cnt[0][j] = 0;
    rep(i, H){
        rep(j, W){
            cnt[i+1][j+1] = cnt[i][j+1]+cnt[i+1][j]-cnt[i][j]+(S[i][j] == '#');
        }
    }

    int dp1[H+1][H+1][W+1][2], dp2[W+1][W+1][H+1][2];
    rep2(h1, 0, H){
        rep2(h2, h1, H){
            int w2 = 0;
            rep2(w1, 0, W){
                chmax(w2, w1);
                while(w2 < W){
                    int s = cnt[h2][w2+1]-cnt[h2][w1]-cnt[h1][w2+1]+cnt[h1][w1];
                    if(s == 0 || s == (h2-h1)*(w2+1-w1)) w2++;
                    else break;
                }
                dp1[h1][h2][w1][0] = w2;
            }
        }
    }
    rep2(w1, 0, W){
        rep2(w2, 0, W){
            int h2 = 0;
            rep2(h1, 0, H){
                chmax(h2, h1);
                while(h2 < H){
                    int s = cnt[h2+1][w2]-cnt[h2+1][w1]-cnt[h1][w2]+cnt[h1][w1];
                    if(s == 0 || s == (h2-h1+1)*(w2-w1)) h2++;
                    else break;
                }
                dp2[w1][w2][h1][0] = h2;
            }
        }
    }

    if(dp1[0][H][0][0] == W){
        cout << 0 << endl;
        return 0;
    }

    rep2(k, 1, 16){
        rep2(h1, 0, H){
            rep2(h2, h1, H){
                rep2(w1, 0, W){
                    int w2;
                    w2 = dp1[h1][h2][w1][(k-1)%2];
                    w2 = dp1[h1][h2][w2][(k-1)%2];
                    dp1[h1][h2][w1][k%2] = w2;
                }
                int w2 = 0;
                rep2(w1, 0, W){
                    chmax(w2, w1);
                    while(w2 < W){
                        int h3;
                        h3 = dp2[w1][w2+1][h1][(k-1)%2];
                        h3 = dp2[w1][w2+1][h3][(k-1)%2];
                        if(h3 >= h2) w2++;
                        else break;
                    }
                    chmax(dp1[h1][h2][w1][k%2], w2);
                }
            }
        }
        
        rep2(w1, 0, W){
            rep2(w2, w1, W){
                rep2(h1, 0, H){
                    int h2;
                    h2 = dp2[w1][w2][h1][(k-1)%2];
                    h2 = dp2[w1][w2][h2][(k-1)%2];
                    dp2[w1][w2][h1][k%2] = h2;
                }
                int h2 = 0;
                rep2(h1, 0, H){
                    chmax(h2, h1);
                    while(h2 < H){
                        int w3;
                        w3 = dp1[h1][h2+1][w1][(k-1)%2];
                        w3 = dp1[h1][h2+1][w3][(k-1)%2];
                        if(w3 >= w2) h2++;
                        else break;
                    }
                    chmax(dp2[w1][w2][h1][k%2], h2);
                }
            }
        }

        if(dp1[0][H][0][k%2] == W){
            cout << k << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 80104