COETEST5

Cho ma trận vuông A kích thước NxN, trong đó:
3 <= N <= 100
1 <= A[i][j] <= 1000
Hãy tính tổng của các hàng, các cột và 2 đường chéo của ma trận. Sau đó in ra tổng lớn nhất trong các tổng vừa tính được.
Ví dụ:

Sau khi tính tổng của các hàng, các cột và 2 đường chéo, ta thu được các tổng như trong hình.
Vậy, kết quả cần in ra là 285, vì 285 là tổng lớn nhất.

Input

Dòng đầu chứa số test case T (T <=50). Mỗi test case được viết trên N+1 dòng
Dòng đầu tiên của mỗi test case chứa kích thước của ma trận N.
N dòng tiếp theo, mỗi dòng chứa N số nguyên, phân biệt nhau bởi dấu cách, chứa các giá trị của ma trận.

Output

In output theo định dạng sau:
Đầu tiên là ký tự "#", tiếp theo là số thứ tự của test case (đánh số từ 1), tiếp theo là 1 khoảng trắng (dấu cách) và cuối cùng là tổng lớn nhất.

Example

Input:
5
3
5 14 14
49 4 5
35 50 17
5
20 3 33 1 45
16 14 42 1 33
28 42 30 35 36
6 42 27 28 9
47 16 28 10 31
6
6 36 21 27 46 30
40 12 2 42 21 11
14 20 1 17 9 14
31 15 32 12 21 24
22 38 31 19 39 9
18 32 11 12 36 38
8
42 32 15 13 10 49 47 8
28 23 50 43 44 19 14 17
17 16 10 22 6 11 4 7
8 24 29 11 3 25 5 44
10 17 12 42 20 8 6 44
35 29 25 9 24 28 41 36
37 50 38 15 35 2 32 45
22 33 33 45 7 49 18 23
10
50 46 6 49 35 9 20 28 49 4
4 33 2 29 26 6 28 34 1 19
30 50 18 10 21 32 40 6 7 40
20 7 16 16 5 39 44 38 7 36
20 32 2 37 41 21 46 35 18 2
10 38 22 35 7 47 27 31 31 18
7 6 13 12 47 44 36 1 31 21
34 36 8 1 13 14 25 47 46 12
36 18 29 3 9 1 50 11 26 33
22 25 37 45 50 15 5 43 9 44

Output:
#1 102
#2 171
#3 172
#4 254
#5 358