lcs

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

SAMPLE INPUT
4 3
1 4 2 3
4 1 2 3
1 2 4 3

SAMPLE OUTPUT
3

Explanation

The longest common subsequence for the sample is subsequence {1, 2, 3}.

Source: hackerearth | Difficulty: MEDIUM


Solutions: