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<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const long double EPS=1e-9;
const long double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
long double ABS(long double a){return max(a,-a);}
char in[220][220];
int sum[220][220];
int rec(int a,int b,int c,int d){
	return sum[c+1][d+1]-sum[a][d+1]-sum[c+1][b]+sum[a][b];
}
int tmp[220];
short to[220][220][220][20];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%s",in[i]);
	int ret=mod;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(in[i][j]=='#'){
				sum[i+1][j+1]++;
			}
		}
	}
	for(int i=0;i<=a;i++){
		for(int j=0;j<=b;j++){
			sum[i][j+1]+=sum[i][j];
		}
	}
	for(int i=0;i<=a;i++){
		for(int j=0;j<=b;j++){
			sum[i+1][j]+=sum[i][j];
		}
	}
	for(int i=b-1;i>=0;i--){
		for(int j=0;j<=16;j++){
			for(int l=i;l<b;l++){
				to[i][a][l][j]=a;
			}
			if(j==0){
				
				for(int l=i;l<b;l++){
					int la=a;
					for(int k=a-1;k>=0;k--){
						while(la>k&&rec(k,i,la-1,l)!=(la-k)*(l-i+1)&&rec(k,i,la-1,l)!=0){
							la--;
						}
						to[i][k][l][j]=la;
			//			printf("%d %d %d %d: %d\n",i,k,l,j,(int)to[i][k][l][j]);
					}
				}
				continue;
			}
			for(int k=a-1;k>=0;k--){
				int bes=i;
				for(int l=i;l<b;l++){
					to[i][k][l][j]=to[i][to[i][k][l][j-1]][l][j-1];
					int las=-mod;
					for(int m=bes;m<l;m++){
						short cur=min(to[i][k][m][j-1],to[m+1][k][l][j-1]);
						if(las<=cur){
							las=cur;
							bes=m;
							to[i][k][l][j]=max(to[i][k][l][j],cur);
						}else break;
					}
			//		printf("%d %d %d %d: %d\n",i,k,l,j,(int)to[i][k][l][j]);
				}
			}

		}
	}
	for(int i=0;i<=16;i++){
		if(to[0][0][b-1][i]==a){
			ret=i;
			break;
		}
	}
	printf("%d\n",ret);
}