#include <iostream>
#include <vector>
#include <string>
#include <cstring>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int H, W;
vector<string> fi;
const int MAX_V = 200;
const int MAX = 20;

long long sum[MAX_V][MAX_V];
int dp1[MAX_V][MAX_V][MAX_V][2];
int dp2[MAX_V][MAX_V][MAX_V][2];

int solve() {
    // 初期化
    sum[0][0] = 0;
    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            sum[h+1][w+1] = -sum[h][w] + sum[h+1][w] + sum[h][w+1] + (fi[h][w] == '#');
        }
    }
    for (int h1 = 0; h1 <= H; ++h1) {
        for (int h2 = h1; h2 <= H; ++h2) {
            int w2 = 0;
            for (int w1 = 0; w1 <= W; ++w1) {
                if (w2 < w1) w2 = w1;
                while (w2 < W &&
                       (sum[h2][w2+1]-sum[h1][w2+1]-sum[h2][w1]+sum[h1][w1] == 0 ||
                        sum[h2][w2+1]-sum[h1][w2+1]-sum[h2][w1]+sum[h1][w1] == (h2-h1)*(w2+1-w1)))
                    ++w2;
                dp1[h1][h2][w1][0] = w2;
            }
        }
    }
    for (int w1 = 0; w1 <= W; ++w1) {
        for (int w2 = w1; w2 <= W; ++w2) {
            int h2 = 0;
            for (int h1 = 0; h1 <= H; ++h1) {
                if (h2 < h1) h2 = h1;
                while (h2 < H &&
                       (sum[h2+1][w2]-sum[h1][w2]-sum[h2+1][w1]+sum[h1][w1] == 0 ||
                        sum[h2+1][w2]-sum[h1][w2]-sum[h2+1][w1]+sum[h1][w1] == (h2+1-h1)*(w2-w1)))
                    ++h2;
                dp2[h1][w1][w2][0] = h2;
            }
        }
    }

    // dp
    int res = MAX;
    for (int k = 0; k+1 < MAX; ++k) {
        // dp1
        for (int h1 = 0; h1 <= H; ++h1) {
            for (int h2 = h1; h2 <= H; ++h2) {
                for (int w1 = 0; w1 <= W; ++w1) {
                    int w = dp1[h1][h2][w1][k%2];
                    chmax(dp1[h1][h2][w1][(k+1)%2], dp1[h1][h2][w][k%2]);
                }
                int w2 = 0;
                for (int w1 = 0; w1 <= W; ++w1) {
                    if (w2 < w1) w2 = w1;
                    while (w2 < W && dp2[dp2[h1][w1][w2+1][k%2]][w1][w2+1][k%2] >= h2)
                        ++w2;
                    chmax(dp1[h1][h2][w1][(k+1)%2], w2);
                }
            }
        }
        // dp2
        for (int w1 = 0; w1 <= W; ++w1) {
            for (int w2 = w1; w2 <= W; ++w2) {
                for (int h1 = 0; h1 <= H; ++h1) {
                    int h = dp2[h1][w1][w2][k%2];
                    chmax(dp2[h1][w1][w2][(k+1)%2], dp2[h][w1][w2][k%2]);
                }
                int h2 = 0;
                for (int h1 = 0; h1 <= H; ++h1) {
                    if (h2 < h1) h2 = h1;
                    while (h2 < H && dp1[h1][h2+1][dp1[h1][h2+1][w1][k%2]][k%2] >= w2)
                        ++h2;
                    chmax(dp2[h1][w1][w2][(k+1)%2], h2);
                }
            }
        }

        if (dp1[0][H][0][k%2] == W) chmin(res, k);
        if (dp2[0][0][W][k%2] == H) chmin(res, k);

        for (int x = 0; x < MAX_V; ++x) {
            for (int y = 0; y < MAX_V; ++y) {
                for (int z = 0; z < MAX_V; ++z) {
                    dp1[x][y][z][k%2] = 0;
                    dp2[x][y][z][k%2] = 0;
                }
            }
        }       
    }
    return res;
}

int main() {
    while (cin >> H >> W) {
        fi.resize(H);
        for (int i = 0; i < H; ++i) cin >> fi[i];
        cout << solve() << endl;
    }
}

Measured memory_bytes: 125568