We define a “NTHUnum” in a sequence is the number of pairs of entries that are out of order with respect to each other. For instance, in the integer sequence “4 1 1 2 5 3”, then the “NTHUnum” is 5, since 4 is greater than four integers to its right and 5 is greater than one integer to its right. In the sequence “1 1 3 5 4 6 6”, the “NTHUnum” is 1 (5 and 4). While the sequence “4 3 2 1”, the “NTHUnum” is 6 (exactly the reverse of sorted)
A set of sequences containing integers will be given. Now using the above approach we want to sort the sequences in ascending order. You have to compute “NTHUnum” for each sequence and then rearrange all the sequences. In order of “NTHUnum”, from “most sorted” to “least sorted”, briefly ascending order.
The first line is an integer i which gives the number of cases. In every case, the first line of each case contains two integers: a positive integer n (0 < n ≤ 50) giving the number of the integers in each sequence; and a positive integer m (0 < m ≤ 1000) giving the number of sequences.
These are followed by m lines, each containing a sequence of n integers.
There is a blank between each integer.
There might have many cases in each testcase.
Input will be terminated by EOF.
Sample Input
2
5 3
2 3 5 6 4
14 15 2 26 3
25 5 6 7 8
3 2
2 3 1
100 90 80
Output the list of input sequences, arranged from “most sorted” to “least sorted” and “NTHUnum” behind in each sequence. You need to rearrange in ascending order. If two or more sequences are equally sorted, list them in the same order they are in the input file. There is a blank line between each case.