darth-vader-the-hero-3

Darth Vader and his stormtroopers were in a battle against the rebels. Darth Vader had to win the battle at any cost in order to fulfil his wish. He is short of stormtroopers, however he had a very powerful weapon DEATH STAR which could be used only once during the war. 

His army was divided into small troops scattered at different locations (which can be contained in a N x M battle ground). The death star, once launched on some troop is capable of killing all the rebels of that troop at a time but cannot harm any rebel soldier in other troops.

The battle is coming to an end and Darth Vader is about to lose. He has only one Death Star but something he knows for sure is that if he is able to kill the maximum possible soldiers with this death star, he and his soldiers definitely have a chance of winning the battle.

So, Darth Vader seeks your help in finding out the maximum number of Rebel soldier he can kill in one strike of the death star and also the total number of Rebel troops gathered against them so that he can dive his army efficiently (the troop killed by death star should also be included).

2 rebel soldiers belong to the same troop if they are at adjacent positions in the battle ground. Therefore, any soldier who is not at some boundary of the batttle ground can have a maximum of 8 adjacent soldiers.

INPUT:::

First line contains single integer T, the number of test cases. First line of each test case contains two space separated integers N and M (size of the battle ground), followed by N lines containing M integers 0 or 1 where 0 means an empty space and 1 means a Rebel soldier.

OUTPUT:::
For every test case, output two space separated integers X and Y where X is the number of Rebel Soldier and Y is the maximum number of Rebel Soldeirs that can be killed by a single strike of the death star.

CONTSTRAINTS:::
1 ≤ T ≤ 10,
1 ≤ N,M ≤ 1000,

SAMPLE INPUT
2
4 6
0 0 0 1 1 0 
1 1 0 0 0 0 
0 1 0 0 0 0 
0 0 1 0 0 0 
6 4
1 1 1 1 
0 0 0 0 
0 1 0 0 
1 0 1 0 
1 0 0 0 
1 0 0 0

SAMPLE OUTPUT
2 4
2 5

Explanation

For the first test case

there are two enemy troops first having positions 1,4 and 1,5 second having positions 2, 1 2, 2 3, 2 4, 3 Therefore the bomb should be exploded on the second troop killing all the 4 enemy soldiers.

Source: hackerearth | Difficulty: MEDIUM_HARD


Solutions: