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>
using namespace std;
inline void upa(int&a,int b){a<b?a=b:0;}
const int N=190;
int H,W,i,j,k,x,A,L[N][N][N],R[N][N][N],U[N][N][N],D[N][N][N];
int L1[N][N][N],R1[N][N][N],U1[N][N][N],D1[N][N][N];
char c[N][N];
template<typename T>inline void work(T*a,T*b,int n,int m){
	for(k=1;k<=m;++k){
		for(i=1;i<n;++i)for(j=n;j>i;--j)upa(b[k][i][j-1],b[k][i][j]);
		for(i=1;i<n;++i)for(j=i+1;j<=n;++j)upa(b[k][i+1][j],b[k][i][j]);
		for(i=1;i<=n;++i)memcpy(a[k][i]+i,b[k][i]+i,n-i+1<<2);
	}
}
inline void upd(int x1,int x2,int y1,int y2){
	upa(U1[x2][y1][y2],x2-x1+1);
	upa(D1[x1][y1][y2],x2-x1+1);
	upa(L1[y2][x1][x2],y2-y1+1);
	upa(R1[y1][x1][x2],y2-y1+1);
}
int main(){
	scanf("%d%d",&H,&W);
	for(i=1;i<=H;++i)scanf("%s",c[i]+1);
	work(L,L1,H,W);
	for(i=W;i;--i)for(j=1;j<=H;++j)for(k=j;k<=H;++k)
		R[i][j][k]=k==j || (c[k][i]==c[k-1][i] && R[i][j][k-1])?(c[k][i]==c[k][i+1]?R[i+1][j][k]:0)+1:0;
	for(i=1;i<=W;++i)for(j=1;j<=H;++j)for(k=j;k<=H;++k)
		L[i][j][k]=k==j || (c[k][i]==c[k-1][i] && L[i][j][k-1])?(c[k][i]==c[k][i-1]?L[i-1][j][k]:0)+1:0;
	for(i=H;i;--i)for(j=1;j<=W;++j)for(k=j;k<=W;++k)
		D[i][j][k]=k==j || (c[i][k]==c[i][k-1] && D[i][j][k-1])?(c[i][k]==c[i+1][k]?D[i+1][j][k]:0)+1:0;
	for(i=1;i<=H;++i)for(j=1;j<=W;++j)for(k=j;k<=W;++k)
		U[i][j][k]=k==j || (c[i][k]==c[i][k-1] && U[i][j][k-1])?(c[i][k]==c[i-1][k]?U[i-1][j][k]:0)+1:0;
	if(R[1][1][H]==W){puts("0");return 0;}
	for(A=1;;++A){
		memset(L1,0,sizeof L1);
		memset(R1,0,sizeof R1);
		memset(U1,0,sizeof U1);
		memset(D1,0,sizeof D1);
		for(i=1;i<=W;++i)for(j=1;j<=H;++j)for(k=j;k<=H;++k){
			if(x=R[i][j][k])upd(j,k,i,i+x+R[i+x][j][k]-1);
			if(x=L[i][j][k])upd(j,k,i-x-L[i-x][j][k]+1,i);
		}
		for(i=1;i<=H;++i)for(j=1;j<=W;++j)for(k=j;k<=W;++k){
			if(x=U[i][j][k])upd(i-x-U[i-x][j][k]+1,i,j,k);
			if(x=D[i][j][k])upd(i+x+D[i+x][j][k]-1,i,j,k);
		}
		work(L,L1,H,W);work(R,R1,H,W);work(U,U1,W,H);work(D,D1,W,H);
		if(R[1][1][H]==W)break;
	}
	printf("%d\n",A);
	return 0;
}