Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

2773.   Fruit Trees
Time Limit: 1.0 Seconds   Memory Limit: 65536K
Total Runs: 257   Accepted Runs: 180



The new campus of UESTC which locates in the suburb of Chengdu is very large and there are many fruit trees in it. WCM likes to eat all kinds of fruits very much. The fruit trees distribute in many different areas. He can select one area and go there to eat all kinds of delicious fruit as many as he can. So he goes directly to the area which contains the most fruit trees. Given the map, you should help him to find the area which contains the most fruit trees.

Given n * n grid map, the position at the i-th row and the j-th column contains a non-negtive integer Aij . If Aij = 0, position (i,j) is the border of the area. If Aij is a positive integer, Aij means the number of fruit trees at that position. For position (i,j), its adjacent positions are (i-1,j), (i+1,j), (i,j-1), and (i,j+1). For two adjacent positions, if the numbers are both positive, the two adjacent positions belong to the same area.

Input

The first line contains a positive integer T, indicating the number of test cases. For each test case, the first line contains one positive integer N . In the next N lines, each line consists of N nonnegative integers. 0 means the border of the areas and positive integer means the number of fruit trees at that place. All numbers are between 0 and 100.

Output

Find out the area which has the most fruit trees and output the number of the fruit trees in it.

Constraints

  • 1 ≤ N ≤ 100
  • Sample Input

    2
    8
    0 0 0 0 0 0 0 0
    0 9 2 1 0 2 1 0
    0 1 0 3 0 5 0 0
    0 3 9 7 0 0 0 0
    0 0 0 0 1 1 0 0
    0 2 3 4 5 6 0 0
    0 0 0 0 0 0 9 0
    0 0 0 0 0 0 0 0
    4
    0 0 0 0
    0 4 0 0
    0 0 20 0
    0 0 0 0
    

    Sample Output

    35
    20
    

    Sample Input/Output Clarification

    In the first sample, there are 4 areas in the map. The number of fruit tress in every area:
    9+2+1+1+3+3+9+7=35;
    2+1+5=8;
    1+1+2+3+4+5+6=22;
    9=9;
    
    So, the maximum of the fruit trees is 35.


    Source: The 5th UESTC Programming Contest Warmup
    Submit   List    Runs   Forum   Statistics

    Tianjin University Online Judge v1.3.0
    Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz