COETEST5

Trò chơi ô ăn quan đã rất nổi tiếng. Ở Việt Nam có rất nhiều biến thể của trò chơi này. Trò chơi ô ăn quan trên đây có luật chơi như sau:

Khi bắt đầu trò chơi, ở trong mỗi ô sẽ có một lượng quân nhất định, cũng có thể không có quân nào. Bạn được quyền chọn một ô để bắt đầu trong phần sân của bạn sau đó chọn đi theo chiều nghịch hoặc chiều thuận kim đồng hồ. Khi chọn xong, bạn sẽ đem số lượng quân ở ô bạn chọn rải sang các ô kế tiếp theo chiều bạn chọn, mỗi ô một quân cho đến khi bạn hết quân. Khi này sẽ có các trường hợp xảy ra.

1. Nếu ô kế tiếp của ô bạn vừa rải quân là một ô có quân thì bạn sẽ tiếp tục lấy số quân ở ô kế tiếp đó, rải sang các ô kế tiếp theo chiều bạn chọn ban đầu. (Tuy nhiên nếu ô kế tiếp của ô bạn vừa rải quân là ô quan có quân thì bạn dừng lại và không ăn thêm được quân nào)
2. Nếu ô kế tiếp của ô bạn vừa rải là một ô trống (không có quân nào):
   • Kiểm tra ô tiếp theo của ô đó, nếu có quân thì bạn có thể ăn được số quân ở ô đó.
   • Nếu ô tiếp theo của ô đó là cũng là ô trống thì bạn dừng lại và không ăn được quân nào.
3. Trong điều kiện 2.1, có một điều kiện tiếp theo, nếu ô tiếp theo của ô bạn vừa ăn quân là một ô trống thì lặp lại trường hợp 2. Tức là nếu ô liền sau đó lại là một ô có quân thì bạn lại tiếp tục ăn số quân ở ô này (điều kiện này chỉ lặp lại 1 lần).

Hãy tìm ra số quân tối đa bạn có thể ăn được.

Input

Dòng đầu tiên của input là số testcase T (T <= 50).

T dòng tiếp theo, mỗi dòng gồm 12 số nguyên N (0 <= N <= 50) trong đó, thứ tự các số được biểu diễn như sau:

Ô 6 và ô 12 là 2 ô quan. Phần sân của bạn từ ô 7 đến ô 11.

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ả.

In ra kết quả là số lượng quân lớn nhất bạn có thể ăn được.

Example

Input:
5
0 5 2 0 5 5 6 4 0 2 3 4
5 4 3 5 6 0 0 5 3 5 0 4
5 3 0 4 3 6 5 6 0 3 5 2
5 0 0 0 6 0 9 1 0 10 4 2
7 3 0 10 5 7 6 4 9 0 8 4 

Output:
#1 5
#2 11
#3 7
#4 15
#5 10