Rishab and Mayank are very good friends. Once Mayank challenged Rishab to answer his question. Since, Rishab is very over confident, he accepted the challenge.

He gave integers N and K to Rishab. Now, K denotes the number of permutations and each permutation contains numbers from 1, 2, 3...n in any order.

Now, for these permutations Rishab has to find the length of the LCS (Longest Common Subsequence). Since, Rishab is not good with Permutations, he has given the task to you.

INPUT

The first line of input contains 2 integers N and K, denoting the numbers and the number of permutations.

Each of next k lines contains the numbers from 1,2 ....n in any order, which tells about the current permutation.

OUTPUT

Output the length of the longest common subsequence per line, do not print newline character at the end.

CONSTRAINTS

1<= N <= 1000

2<= K <=5