COETEST5

Trong một cuộc chiến tranh, các quốc gia đem quân đội của mình đi xâm lược các quốc gia khác với mục đích mở rộng lãnh thổ của mình.
Quy tắc cuộc chiến như sau:
- Nếu nước bị tấn công có số quân nhỏ hơn hoặc bằng một nửa số quân của nước tấn công thì nước bị tấn công sẽ lập tức đầu hàng và toàn bộ số quân của nước bị tấn công sẽ bị nước tấn công thâu tóm.
- Nếu nước bị tấn công có số quân lớn hơn một nửa số quân của nước tấn công thì 2 bên sẽ chiến đấu với nhau với tỉ lệ tiêu hao binh lực là 1:1, đất nước nào hết quân trước thì sẽ thua.
- Khi tấn công, nước tấn công chỉ được đi theo 1 hướng duy nhất từ trái qua phải hoặc từ phải qua trái mà không được quay lại trong quá trình tấn công.
- Đất nước tấn công sẽ tấn công các nước khác liên tục cho đến khi hết số quân mà nước đó có.
Ví dụ: Có 6 nước với số quân như hình dưới:

Giả sử nước C là nước đi tấn công các nước khác. Nước C tấn công theo hướng từ trái qua phải.
Đầu tiên nước C sẽ gặp nước D với số quân là 9. Vì 16/2 < 9 nên 2 nước đánh nhau với tỉ lệ tiêu hao binh lực là 1:1.
Vậy sau khi đánh xong số quân của nước C còn lại là 16 - 9 = 7.
Vì không được đổi hướng khi đang tấn công nên nước C tiếp tục tấn công đến nước E với số quân là 35.
Vì 7/2 < 35 nên 2 nước đánh nhau và nước E dành chiến thắng vì nước C hết quân trước.

Vậy tổng kết là nước C đã đánh bại được số quân là 9 + 7 = 16.
Giả sử nước C tấn công theo hướng từ phải qua trái
Áp dụng quy tắc trên ta thu được kết quả như hình dưới.

Vậy tổng kết lại nước C đã đánh bại được số quân là 8 + 20 = 28.
Như vậy số quân tối đa mà nước C đánh bại được là 28 quân.
Hãy viết chương trình tính xem nước nào đánh bại được nhiều quân nhất và in ra số quân đánh bại nhiều nhất đó.
Lưu ý kiểu dữ liệu của kết quả

Input

Dòng đầu là số lượng test case. Mỗi test case được viết trên 2 dòng.
Dòng 1 là số lượng đất nước N (N <= 1000).
Dòng tiếp theo là N số biểu thị số quân mỗi nước (số quân mỗi nước <= 10⁹).

Output

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

Example

Input:
5 
10 
689 767 390 36 938 916 165 459 503 508 
10 
591 330 154 9 94 189 653 259 419 485 
10 
220 454 763 840 909 384 108 739 880 570 
20 
47 144 103 10 177 1 199 30 113 4 60 134 126 134 181 88 51 71 23 174 
20 
6 24 148 48 60 141 89 125 177 111 195 114 147 116 147 99 95 91 24 54 

Output:
#1 1790 
#2 1367
#3 1893
#4 1696 
#5 364