Problem: Note the unusual memory limit.

For a rectangular grid where each square is painted white or black, we define its complexity as follows:

* If all the squares are black or all the squares are white, the complexity is 0.
* Otherwise, divide the grid into two subgrids by a line parallel to one of the sides of the grid, and let c_1 and c_2 be the complexities of the subgrids. There can be multiple ways to perform the division, and let m be the minimum value of \max(c_1, c_2) in those divisions. The complexity of the grid is m+1.



You are given a grid with H horizontal rows and W vertical columns where each square is painted white or black. HW characters from A_{11} to A_{HW} represent the colors of the squares. A_{ij} is `#` if the square at the i-th row from the top and the j-th column from the left is black, and A_{ij} is `.` if that square is white.

Find the complexity of the given grid.

Constraints

* 1 \leq H,W \leq 185
* A_{ij} is `#` or `.`.

Input

Input is given from Standard Input in the following format:


H W
A_{11}A_{12}...A_{1W}
:
A_{H1}A_{H2}...A_{HW}


Output

Print the complexity of the given grid.

Examples

Input

3 3
...
.##
.##


Output

2


Input

6 7
.####.#
....#.
....#.
....#.
.####.#
....##


Output

4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define rep2D(l, r, n) \
	for (int __repeat_gap = 0; __repeat_gap < n; ++__repeat_gap) \
		for (l = 1, r = l + __repeat_gap; r <= n; ++l, ++r)
#define per2D(l, r, n) \
	for (int __repeat_gap = n - 1; __repeat_gap > 0; --__repeat_gap) \
		for (l = 1, r = l + __repeat_gap; r <= n; ++l, ++r)

typedef unsigned char u8;
const int N = 187;

int R, C;
int sum[N][N];
u8 ri[16][N][N][N], dn[16][N][N][N];
// right[k][r1][r2][c], down[k][c1][c2][r]

inline void up(u8 &x, const u8 y) {x < y ? x = y : 0;}
inline int S(int r1, int c1, int r2, int c2) {return sum[r2][c2] - sum[r2][c1 - 1] - sum[r1 - 1][c2] + sum[r1 - 1][c1 - 1];}

int main() {
	int i, j, r1, r2, c1, c2, cur, la, ans;
	char tmp[N]; u8 *f, *g;
	scanf("%d%d", &R, &C);
	for (i = 1; i <= R; ++i)
		for (scanf("%s", tmp + 1), j = 1; j <= C; ++j)
			sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + (tmp[j] & 1);
	rep2D(r1, r2, R) {
		f = ri[0][r1][r2], la = -1;
		for (j = C; j; --j, la = cur)
			cur = S(r1, j, r2, j), f[j] = (cur && cur != r2 - r1 + 1 ? j - 1 : cur == la ? f[j + 1] : j);
	}
	rep2D(c1, c2, C) {
		f = dn[0][c1][c2], la = -1;
		for (i = R; i; --i, la = cur)
			cur = S(i, c1, i, c2), f[i] = (cur && cur != c2 - c1 + 1 ? i - 1 : cur == la ? f[i + 1] : i);
	}
	// main_loop
	for (ans = 0; ans < 15 && ri[ans][1][R][1] < C; ) {
		rep2D(r1, r2, R) {
			f = ri[ans][r1][r2], g = ri[ans + 1][r1][r2];
			for (j = 1; j <= C; ++j) up(g[j], f[j] == C ? C : f[f[j] + 1]), up(dn[ans + 1][j][g[j]][r1], r2);
		}
		rep2D(c1, c2, C) {
			f = dn[ans][c1][c2], g = dn[ans + 1][c1][c2];
			for (i = 1; i <= R; ++i) up(g[i], f[i] == R ? R : f[f[i] + 1]), up(ri[ans + 1][i][g[i]][c1], c2);
		}
		++ans;
		per2D(r1, r2, R)
			for (j = 1; j <= C; ++j)
				up(ri[ans][r1][r2 - 1][j], ri[ans][r1][r2][j]), up(ri[ans][r1 + 1][r2][j], ri[ans][r1][r2][j]);
		per2D(c1, c2, C)
			for (i = 1; i <= R; ++i)
				up(dn[ans][c1][c2 - 1][i], dn[ans][c1][c2][i]), up(dn[ans][c1 + 1][c2][i], dn[ans][c1][c2][i]);
	}
	ans += ri[ans][1][R][1] < C, printf("%d\n", ans);
	return 0;
}