Problem: Great performance strategy

Taro, an examinee, participated in an N-day study camp. In this training camp, M subjects are tested every day, and after the training camp, a report card with all the test scores is distributed. The report card consists of N sheets of paper, and on the i-th sheet, only the subject names and scores of the tests of all M subjects on the i-day are printed.

Taro noticed that the date was not written on the report card, and decided to add some work before giving the report card to his mother. By rearranging the order of the papers in the report card and writing the page numbers in order from the first sheet to make a booklet, a "fake report card" was created. Taro's purpose is to maximize the number of subjects whose test scores are monotonously increasing with respect to page numbers in the "False Report Card".

When Taro makes a "false grade report", find the maximum number of subjects whose test scores are monotonously increasing with respect to the page number.

However, the N-day test score is a broad monotonous increase with respect to the page number. For 1 ≤ i <N, the score on the i + 1 sheet is the score on the i-th sheet. It means that it is the above.

Input

The input consists of 50 or less datasets. Each dataset is represented in the following format.

> N M a11 ... a1M ... aN1 ... aNM

The first line gives the number of days N and the number of subjects M for the study camp. N is an integer between 1 and 103, and M is an integer between 1 and 40.

Taro's score is given to the following N lines. Each line consists of M integers, where aij is the score of Taro-kun's subject j on day i, and aij is an integer between 0 and 103.

The end of the input is represented by a line of two zeros.

Output

For each dataset, output the maximum number of subjects whose test scores are monotonously increasing with respect to the page number on one line.

Sample Input


3 3
one two Three
2 1 3
3 3 3
8 5
3 3 4 3 4
2 1 2 3 2
7 9 7 8 7
3 4 3 3 4
1 2 2 3 2
4 5 6 5 6
7 9 7 7 8
4 5 5 6 6
5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
5 9
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5
0 0


Output for the Sample Input


2
3
1
9






Example

Input

3 3
1 2 3
2 1 3
3 3 3
8 5
3 3 4 3 4
2 1 2 3 2
7 9 7 8 7
3 4 3 3 4
1 2 2 3 2
4 5 6 5 6
7 9 7 7 8
4 5 5 6 6
5 5
1 2 3 4 5
2 3 4 5 1
3 4 5 1 2
4 5 1 2 3
5 1 2 3 4
5 9
1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5
0 0


Output

2
3
1
9

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 45

enum Type{
	UNDEFINED,
	TRUE,
	FALSE,
};

struct Info{
	Info(int arg_main_value,int arg_sub_value){
		main_value = arg_main_value;
		sub_value = arg_sub_value;
	}
	bool operator<(const struct Info &arg) const{

		if(main_value != arg.main_value){

			return main_value < arg.main_value;
		}else{

			return sub_value < arg.sub_value;
		}
	}

	int main_value,sub_value;
};

int N,M;
int table[1005][SIZE];
vector<int> G[SIZE];
vector<Info> info;
int ans;
Type type[SIZE];

void recursive(int node_id,int count){

	if(count+(M-node_id+1) <= ans)return;

	if(node_id == M){

		ans = max(ans,count);

		return;
	}

	if(type[node_id] != UNDEFINED){ //決定済

		recursive(node_id+1,count);
		return;
	}

	Type pre[SIZE];
	for(int i = 0; i < M; i++){
		pre[i] = type[i];
	}

	type[node_id] = FALSE;
	recursive(node_id+1,count);

	for(int i = 0; i < M; i++){

		type[i] = pre[i];
	}

	type[node_id] = TRUE;
	for(int i = 0; i < G[node_id].size(); i++){

		type[G[node_id][i]] = FALSE;
	}
	recursive(node_id+1,count+1);
}

void func(){

	info.clear();

	for(int i = 0; i < SIZE; i++){
		G[i].clear();
	}

	for(int i = 0; i < N; i++){
		for(int k = 0; k < M; k++){
			scanf("%d",&table[i][k]);
		}
	}

	//同時に昇順にできないペアを探す
	for(int i = 0; i < M-1; i++){
		for(int k = i+1; k < M; k++){

			info.clear();

			for(int a = 0; a < N; a++){

				info.push_back(Info(table[a][i],table[a][k]));
			}

			sort(info.begin(),info.end());

			bool FLG = true;

			for(int a = 0; a < N-1; a++){
				for(int b = a+1; b < N; b++){
					if(info[a].main_value < info[b].main_value && info[a].sub_value > info[b].sub_value){
						FLG = false;
						break;
					}
				}
				if(!FLG)break;
			}

			if(!FLG){

				G[i].push_back(k);
				G[k].push_back(i);
			}
		}
	}

	ans = 1;
	int first_count = 0;

	for(int i = 0; i < M; i++){

		if(G[i].size() > 0){
			type[i] = UNDEFINED;
		}else{
			type[i] = TRUE; //無条件採用
			first_count++;
		}
	}

	recursive(0,first_count);

	printf("%d\n",ans);
}

int main(){

	while(true){
		scanf("%d %d",&N,&M);
		if(N == 0 && M == 0)break;

		func();
	}

	return 0;
}