COETEST5

[Problem]

Một anh shipper cần giao hàng đến N điểm, thời gian giao hàng sẽ được tính bằng tổng thời gian từ lúc xuất phát rồi đi đến các địa điểm khác và quay trở lại địa điểm ban đầu.

Thời gian giao hàng được gọi là tối ưu nhất khi thời gian giao hàng là ít nhất.

Cho thông tin về thời gian T di chuyển giữa các địa điểm cần giao hàng (5 <= T <= 100). Hãy giúp anh ta tìm 1 điểm xuất phát ban đầu trong N địa điểm để đạt được thời gian giao hàng được tối ưu nhất.

Người giao hàng sẽ di chuyển theo các nguyên tắc sau:     

- Từ vị trí hiện tại, anh ta sẽ đi đến vị trí giao hàng tiếp theo sao cho thỏa mãi điều kiện là vị trí tiếp đó là gần anh ta nhất.

- Nếu có nhiều hơn một vị trí gần anh ta nhất thì anh ta sẽ di chuyển đếm điểm có giá trị nhỏ hơn.

[Examble_1]

Th1: nếu đi theo lộ trình 1 >> 5 >> 2 >> 4 >> 3 >> 1
Tổng thời gian giao hàng là : 5 + 8 + 9 + 6 +16  = 44

Th2: nếu đi theo lộ trình 2 >> 5 >> 1 >> 4 >> 3 >> 2

Tổng thời gian giao hàng là : 8 + 5 + 16 + 6 + 23  = 58

[Examble_2]

đi theo lộ trình 1 >> 5 >> 2 >> 4 >> 3 >> 1 => SAI

đi theo lội trình 1 >> 2 >> 5 >> 4 >> 3 >> 1 = > ĐÚNG

 

Input:

Dòng đầu tiên là số lượng test case T (T <= 50).

Thông tin về mỗi test case như sau :

Dòng đầu tiên là số N là số địa điểm cần giao hàng (5 <= N <= 50)

Trong N dòng tiếp theo, mỗi dòng thứ i gồm N số nguyên dương T( 5 <= T <= 100) tương ứng là thời gian di chuyển từ điểm thứ i đến N điểm giao hàng.

Output:

Đưa ra output trên T dòng tương ứng với T test case.

Mỗi test case in ra "#tc" với tc là số thứ tự của test case, đánh số bắt đầu từ 1, tiếp theo là một dấu cách và kết quả tương ứng của test case đó.

Kết quả in ra là tổng thời gian ngắn nhất để giao hàng đến tất cả địa điểm và quay lại điểm xuất phát.

Example

Input:
2
5
0 10 16 16 5
10 0 23 9 8
16 23 0 6 61
16 9 6 0 16
5 8 61 16 0
5
0 5 20 16 5
5 0 23 9 8
20 23 0 6 61
16 9 6 0 16
5 8 61 16 0

Output:
#1 44
#2 55