13850번 - University Rankings 다국어

Doctor Bob is working on creating university rankings at International Company for Promoting Colleges. 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 is hard to determine which university is better, when comparing two universities with each other. Fortunately, Bob has advanced a new concept named absolutely better, with which the problem above can be partially solved.

Now, we take 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 ranking of each department is as follows, where X > Y means X have a better CS department than Y:

• The ranking of CS: X > Y > Z
• The ranking of EE: X > Z > Y
• The ranking of FLS: Z > X > Y

Obviously, all departments of University X are better than those of University Y. Then, we say 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 Ui is absolutely better that U_j (for any i < j). Could you tell Bob the maximum value of k? Note that the universities are represented by numbers in the input.

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

The first line of each test case is two positive integer N, M (0 < N, M ≤ 400), where N is the number of universities and M is the number of departments. And then M lines follow. The k-th (1 ≤ k ≤ M) line contains N numbers U_k,i (1 ≤ i ≤ N, 1 ≤ U_k,i ≤ N), indicating the ranking of the k-th department. If University U_k,i precedes to University U_k,j in line k, then the k-th department of U_k,i is better than the k-th department of U_k,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.