成績上昇大作戦

受験生の太郎君は N 日間の勉強合宿に参加した． この合宿では毎日 M 科目のテストを行い， 合宿の終了後にはすべてのテストの点数が書かれた成績表が配られる． 成績表は N 枚の紙からなっており，i 枚目の紙には i 日目の全 M 科目のテストの科目名と点数のみが印刷されている．

成績表に日付が書かれていないことに気付いた太郎君は，お母さんに成績表を渡す前に細工を加えることにした． 成績表の紙の順番を並べ替え，さらに1枚目から順番にページ番号を書き込んで冊子にすることによって「偽りの成績表」を作ったのだ． 太郎君の目的は，「偽りの成績表」でテストの点数がページ番号に対して広義単調増加している科目の個数を最大化することである．

太郎君が「偽りの成績表」を作るとき，テストの点数がページ番号に対して広義単調増加である科目の個数の最大値を求めよ．

ただし，N 日間のテストの点数がページ番号に対して広義単調増加であるとは 1 ≤ i < N に対して i+1 枚目に記載されている点数が i 枚目に記載されている点数以上であることを意味する．

Input

入力は 50 個以下のデータセットからなる． 各データセットは次の形式で表される．

N M a₁₁ ... a_1M ... a_N1 ... a_NM

1行目には，勉強合宿の日数 N と科目数 M が与えられる．N は 1 以上 10³ 以下の整数で，M は 1 以上 40 以下の整数である．

続く N 行には太郎君の点数が与えられる．各行は M 個の整数からなっており a_ij は太郎君の i 日目の科目 j の点数であり，a_ij は 0 以上 10³ 以下の整数である．

入力の終わりは，2 つのゼロからなる行で表される．

Output

各データセットについて，テストの点数がページ番号に対して広義単調増加である科目の個数の最大値を 1 行に出力せよ．

Sample 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 for the Sample Input

2
3
1
9