22185_UniversityRankings

At present, the university rankings are very popular. They help senior high school students to choose universities for further study. For example, you can find the CHINESE UNIVERSITY RANKINGS at http://www.netbig.com/.

Figure 1

As we know, a university usually has many different departments, such as department of Computer Science (CS), department of Electronic Engineering (EE), and School of Foreign Languages (FLS). Some of them are quite good when comparing to the other universities, but others are not. So, most of the university rankings are composed of several ranking lists, each list for one department.

But here comes a problem that sometimes it's hard to determine which university is better, when comparing two universities with each other. Fortunately, Doctor Bob has advanced a new concept named "absolutely better", with which the problem above can be partially solved.

Now, here is an example to explain the concept "absolutely better":

Assume that there are three universities (X, Y, Z) and every university has three departments: CS, EE and FLS. And the rankings of different departments are as followed:

The ranking of CS: X > Y > Z ( X > Y means X have a better CS department than Y )

The ranking of EE: X > Z > Y

The ranking of FLS: Z > X > Y

Obviously, each department of University X is better than that of University Y. Then, it's called that X is absolutely better than Y. Using the "absolutely better" concept, it becomes possible to compare some pairs of the universities.

Now Bob has the complete rankings of different departments of many universities, and he wants to find k universities ( U₁, ..., U_k ) such that U_i is absolutely better that U_j ( for any i < j ). Could you tell Bob the maximum value of k ?

The first line of the input is a positive integer C. C is the number of test cases followed.

The first line of each test case is two positive integer N, M ( 0 < N, M ≤ 100 ), N is the number of universities and M is the number of departments. And then M lines follow. The i-th ( 1 ≤ i ≤ M ) line contains N numbers U_i ( 1 ≤ i ≤ N, 1 ≤ U_i ≤ N ), indicating the ranking of the i-th department. If University U_i precedes to University U_j in line k, then the k-th department of U_i is better than the k-th department of U_j.

The output should consist of C lines, one line for each test case. Each line only contains one integer -- the maximum value of k as described above. No redundant spaces are needed.

1
3 3
1 2 3
1 3 2
3 1 2

2