import scala.annotation.tailrec
import scala.collection.mutable
import scala.io.StdIn._

object Main extends App {

  solve()
  @tailrec def solve(): Unit = {
    val Array(n, m) = readLine.trim.split(' ').map(_.toInt)
    if (n == 0 && m == 0) return
    val scores = Array.tabulate(n){_ ⇒ readLine.trim.split(' ').map(_.toInt)}
    val subjects = Array.tabulate(m){i ⇒ (0 until n).sortBy(d ⇒ scores(d)(i)).toArray}
    val nodes = Array.fill(m){Nil: List[Int]}
    for (i ← 1 until m; j ← 0 until i) {
      var isCo = true
      var prev = 0
      for (d ← (0 until n).sortWith((a, b) ⇒ if (scores(a)(i) == scores(b)(i)) scores(a)(j) < scores(b)(j) else scores(a)(i) < scores(b)(i)) if isCo) {
        if (prev > scores(d)(j)) {
          isCo = false
        }
        prev = scores(d)(j)
      }
      if (!isCo) {
        nodes(i) ::= j
        nodes(j) ::= i
      }
    }
    println(calMax(nodes))
    solve()
  }
  object Flag {
    def fill(size: Int): Flag = new Flag((1L << size) - 1)
  }
  class Flag(val toLong: Long) {
    def each: List[Int] = {
      var state = toLong
      var res = Nil: List[Int]
      for (i ← 0 until 63 if state != 0){
        if ((state & 1) == 1) {
          res ::= i
        }
        state >>= 1
      }
      res
    }
    def add(flag: Int*): Flag = {
      new Flag(flag.foldLeft(toLong){case (acc, i) ⇒ acc | (1L << i)})
    }
    def remove(flag: Int*): Flag = {
      new Flag(flag.foldLeft(toLong){case (acc, i) ⇒ acc & ~(1L << i)})
    }
    def isOn(flag: Int): Boolean = ((1L << flag) & toLong) != 0
    def isEmpty: Boolean = toLong == 0L
  }


  def calMax(nodes: Array[List[Int]]): Int = {
    val default = nodes.indices.filter{i ⇒
      nodes(i) match {
        case Nil ⇒ true
        case j::Nil if i < j || nodes(j).length > 1 ⇒ true
        case _ ⇒ false
      }
    }
    val flag = Flag.fill(nodes.length).remove(default.flatMap(nodes):_*).remove(default:_*)
    def calMax(set: Flag, nodes: Array[List[Int]])(implicit memo: mutable.Map[Long, Int]): Int = {
      memo.getOrElseUpdate(set.toLong,
        {
          if (set.isEmpty) {
            0
          }else {
            val max = set.each.maxBy { i ⇒ nodes(i).count(j ⇒ set.isOn(j)) }
            math.max(1 + calMax(set.remove(max).remove(nodes(max):_*), nodes), calMax(set.remove(max), nodes))
          }
        }
      )
    }
    calMax(flag, nodes)(mutable.Map[Long, Int]()) + default.length
  }
}

