Description

Last saturday, Paul, Ivo and Nick went to a bowling alley. The hired a lane for one hour, and played three games. In this casual game play, the guys were simply counting the number of games they won: the overall winner would be the one who won the most games. (In case of a tie, they would have had to figure out another way to pronounce the winner.)

This time, Paul won two games and Nick one, so Paul was pronounced the winner. Ivo wondered how it was possible he lost all three games even though he felt his scores were not too bad. So he looked again at the scoreboard and saw this:

Game	1	2	3
Paul	102	86	94
Ivo	98	73	112
Nick	95	84	125

Paul indeed won two games, and Nick one, but Ivo noted that if he would have played his games in another order, namely 112-98-73, he would have won the two games, and Paul none!

Ivo's remark is not as unreasonable as one might think at first glance: in bowling, each game is played independent of the other players, except perhaps for some psychological side effects. The successive scores of an individual player can also be assumed to be more or less independent and identically distributed.

Ivo wisely kept his remarks to himself last Saturday, but later he started to think about using his idea of 'potential number of wins' as a measure of performance. He concluded that it would also be interesting to know the minimum number of wins for each player. Also, it would be nice not only to allow permutation of the games of the player whose number of wins is being maximized or minimized, but also permutation of the games of the other players. Finally, Ivo has to define when exactly a player 'wins' a game: a player wins a game if and only if his score is strictly greater than the score of each of the other players.

Ivo asks you to write a program that calculates fro each player i:

• mi, the minimal number of games player i would have won, regardless of the permutation of the scores of each individual player and
• Mi, the maximal number of games player i could have won if the scores of each individual player were permuted optimally to that purpose

Input

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:

• One line with two integers P and G, separated by a single space, that indicate the number of players and the number of games respectively(2 <= P <= 100, 2 <= G <= 1000).
• P lines, one for each player, each with G integers, separated by single spaces: the successive scores for that player.

Each score is between 0 and 300 (both inclusive).

Output

For every test case in the input, the output should contain P lines, one for each player in the input. On the i^th line should be two integers, separated by a single space: mi, followd by Mi.

2
3 3
102 86 94
98 73 112
95 84 125
3 4
100 110 112 116
98 112 110 112
90 98 113 113

0 2
0 2
1 2
1 3
0 2
1 2

Source

The 2006 Benelux Algorithm Programming Contest