EIU Programming Page for CIT

Hậu là một thợ xây quái đảng trong ngành xây dựng, một hôm xem tin tức về kim tự tháp, Hậu cho rằng những kim tự tháp này được xây dựng quá tầm thường. Sau 1 hồi suy nghĩ anh đã cho ra lò những bản thiết kế kim tự tháp bất ổn, các kim tự tháp của anh được xây lúc riêng lẻ, lúc thì dính lấy nhau.

Bây giờ, Hậu muốn cắt các miếng ván để tạo thành mô hình, hãy giúp anh ấy tính xem anh ấy cần bao nhiều miếng ván để hoàn thành mô hình. Mô hình được mô tả như hình vẽ, mỗi 1 khối là 1 miếng ván cần cắt (thỉnh thoảng có những tầng kim tự tháp cao hơn 1 tầng nhưng do Hậu có miếng ván dày hơn nên chỉ cần cắt 1 tấm ván từ đó. VD:  0 2 2 0).

Input

Dòng đầu tiên là số nguyên T, số bộ dữ liệu (1 <= T <= 1000).

Mỗi bộ dữ liệu gồm số thứ tự và 12 số nguyên không âm tượng trưng cho bản thiết kế kim tự tháp, số đầu và cuối của bản thiết kế luôn luôn bằng 0.

Note: 30% testcases có giới hạn chiều cao kim tự tháp là 100, 40% testcases có giới hạn 1000, và 30% có giới hạn 10^9.

Output

Mỗi bộ dữ liệu, xuất ra số thứ tự của bộ dữ liệu và số ván cần cắt trên một dòng, cách nhau bởi khoảng trắng.

Example

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

Output:
1 4
2 8
3 6
4 10