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 llong long long
#define mkpr make_pair
#define riterator reverse_iterator
using namespace std;

inline int read()
{
	int x = 0,f = 1; char ch = getchar();
	for(;!isdigit(ch);ch=getchar()) {if(ch=='-') f = -1;}
	for(; isdigit(ch);ch=getchar()) {x = x*10+ch-48;}
	return x*f;
}

const int N = 185;
int fx[N+3][N+3],fy[N+3][N+3];
int gx[N+3][N+3][N+3],gy[N+3][N+3][N+3];
int hx[N+3][N+3][N+3],hy[N+3][N+3][N+3];
char a[N+3][N+3];
int n,m;

void updmax(int &x,int y) {x = max(x,y);}

void dp()
{
	for(int lx=1; lx<=n; lx++) for(int ly=1; ly<=m; ly++) for(int rx=lx; rx<=n; rx++)
	{
		gx[lx][ly][rx] += gx[lx][ly+gx[lx][ly][rx]][rx];
		if(gx[lx][ly][rx]>0) {updmax(hy[lx][ly][ly+gx[lx][ly][rx]-1],rx-lx+1);}
	}
	for(int lx=1; lx<=n; lx++) for(int ly=1; ly<=m; ly++) for(int ry=ly; ry<=m; ry++)
	{
		gy[lx][ly][ry] += gy[lx+gy[lx][ly][ry]][ly][ry];
		if(gy[lx][ly][ry]>0) {updmax(hx[lx][ly][lx+gy[lx][ly][ry]-1],ry-ly+1);}
	}
	for(int lx=1; lx<=n; lx++) for(int ly=1; ly<=m; ly++) for(int rx=n; rx>=lx; rx--)
	{
		if(rx<n) updmax(hx[lx][ly][rx],hx[lx][ly][rx+1]);
		updmax(gx[lx][ly][rx],hx[lx][ly][rx]);
	}
	for(int lx=1; lx<=n; lx++) for(int ly=1; ly<=m; ly++) for(int ry=m; ry>=ly; ry--)
	{
		if(ry<m) updmax(hy[lx][ly][ry],hy[lx][ly][ry+1]);
		updmax(gy[lx][ly][ry],hy[lx][ly][ry]);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) scanf("%s",a[i]+1);
	for(int i=1; i<=n; i++) for(int j=m; j>=1; j--)
	{
		fx[i][j] = a[i][j]==a[i][j+1]?fx[i][j+1]+1:1;
	}
	for(int j=1; j<=m; j++) for(int i=n; i>=1; i--)
	{
		fy[i][j] = a[i][j]==a[i+1][j]?fy[i+1][j]+1:1;
	}
	for(int lx=n; lx>=1; lx--) for(int ly=1; ly<=m; ly++)
	{
		int z = gx[lx][ly][lx] = fx[lx][ly];
		if(a[lx][ly]==a[lx+1][ly])
		{
			for(int rx=lx+1; rx<=n; rx++)
			{
				gx[lx][ly][rx] = min(z,gx[lx+1][ly][rx]);
			}
		}
	}
	for(int ly=m; ly>=1; ly--) for(int lx=1; lx<=n; lx++)
	{
		int z = gy[lx][ly][ly] = fy[lx][ly];
		if(a[lx][ly]==a[lx][ly+1])
		{
			for(int ry=ly+1; ry<=m; ry++)
			{
				gy[lx][ly][ry] = min(z,gy[lx][ly+1][ry]);
			}
		}
	}
	int ans = 0;
	while(gx[1][1][n]<m)
	{
		ans++;
		dp();
	}
	printf("%d\n",ans);
	return 0;
}