Maximum sum on a torus

Ένα πλέγμα που περιτυλίγεται τόσο οριζόντια όσο και κάθετα ονομάζεται τόρος. Δεδομένου ενός τόρου όπου κάθε κελί περιέχει έναν ακέραιο αριθμό, προσδιορίστε το υποορθογώνιο με το μεγαλύτερο άθροισμα. Το άθροισμα ενός υποορθογωνίου είναι το άθροισμα όλων των στοιχείων του εν λόγω ορθογωνίου. Το παρακάτω πλέγμα δείχνει έναν τόρο όπου το μέγιστο υποορθογώνιο έχει σκιασθεί.

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τον αριθμό των αρχείων ελέγχου (το πολύ ~18~).

Κάθε αρχείο θα αρχίζει με έναν ακέραιο αριθμό ~N\;(1 \le N \le 75)~ που προσδιορίζει το μέγεθος του τόρου (πάντα τετράγωνο).

Στη συνέχεια θα ακολουθούν ~N~ γραμμές που περιγράφουν τον τόρο και κάθε γραμμή θα περιέχει ~N~ ακέραιους αριθμούς μεταξύ ~-100~ και ~100~, συμπεριλαμβανομένων.

Έξοδος

Για κάθε αρχείο ελέγχου, εξάγετε μια γραμμή που να περιέχει έναν ακέραιο αριθμό: το μέγιστο άθροισμα ενός υπο-ορθογωνίου εντός του του τόρου.

Παράδειγμα

input

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

output

15
45