Three friends Aditya ,Saransh and Aviral are spreading awareness regarding COVID 19. They have come across " + " sign that is use by hospitals, nursing homes, clinics, dispensary, ambulances, etc.
This sign is used by Doctors so that they can be easily identified, especially during an emergency.
They are Given a N X N binary matrix and their task is to find size of the largest ‘+’ formed by all 1s. Help them to complete the task.
Input:
First line contains an integer T. T test cases follow.
First line of each case contains integer N that is order of square matrix (N*N).
Then it contains N*N elements (all the elements of the matrix)
Output:
For each test case, output is the integer M (it is the total number of 1's present in the "+" sign);
Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 10000
Sample Input: Sample Output:
2
5 5
1 0 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 1
7 9
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
Explanation:
In first test case where input is 5 (value of N),we can observe a "+" sign formed in which total 1's is 5;
In Second test case where input is 7 (value of N),,we can observe a "+" sign formed in which total 1's is 9;
Note: Copy and paste is disabled for all the questions. Try not to use other ides.