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:
//第8回シンデレラガール総選挙は是非本田未央ちゃんに投票をお願いします！
//ファンのことも他のアイドルの子たちのことも本当に大事にしてて、今まで周りに色んなものを与えてくれました。
//今度は私たちが未央ちゃんにお返しをする番です。みんなでガラスの靴を履かせてあげましょう！
// #本田未央を一番星に #本田未央を令和のシンデレラガールに #第8回シンデレラガール総選挙
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define N 190
#define M 20
short dp[N][N][N][M];
int sum[N][N];
string ma[N];
int h,W;
int num(int lx,int hx,int ly,int hy){
	return sum[hx][hy]-sum[hx][ly]-sum[lx][hy]+sum[lx][ly];
}
int cal(int x,int y,int z,int w){
	if(dp[x][y][z][w]>=0) return dp[x][y][z][w];
	if(w==0){
		int lo=z,hi=W;
			if(x==0 && y==3 && z==0 && w==0){
				//cout<<lo<<hi<<endl;
			}
		while(hi>lo){
			int mi=(hi+lo+1)/2;
			if(num(x,y,z,mi)==0 || num(x,y,z,mi)==(y-x)*(mi-z)) lo=mi;
			else hi=mi-1;
		}
		//cout<<x<<' '<<y<<' '<<z<<' '<<w<<' '<<lo<<endl;
		return dp[x][y][z][w]=lo;
	}
	int ret=cal(x,y,cal(x,y,z,w-1),w-1),lo=x+1,hi=y-1;
	if(hi>=lo){
		while(hi>lo){
			int mi=(hi+lo+1)/2;
			if(cal(x,mi,z,w-1)<cal(mi,y,z,w-1)) hi=mi-1;else lo=mi;
		}
		ret=max(ret,min(cal(x,lo,z,w-1),cal(lo,y,z,w-1)));
		if(lo<y-1) ret=max(ret,min(cal(x,lo+1,z,w-1),cal(lo+1,y,z,w-1)));
	}
	//cout<<x<<' '<<y<<' '<<z<<' '<<w<<' '<<ret<<endl;
	return dp[x][y][z][w]=ret;
}
int main()
{
	cin>>h>>W;
	rep(i,h) cin>>ma[i];
	memset(sum,0,sizeof(sum));
	rep(i,h) rep(j,W){
		sum[i+1][j+1]=sum[i+1][j]+sum[i][j+1]-sum[i][j];
		if(ma[i][j]=='#') sum[i+1][j+1]++;
	}
	memset(dp,-1,sizeof(dp));
	//cout<<cal(0,3,0,1)<<endl;
	//cout<<cal(1,3,1,0)<<endl;
	rep(i,M){
		if(cal(0,h,0,i)>=W){
			cout<<i<<endl;return 0;
		}
	}
}