Ở level 1 của trò chơi BBTAN remix (PROB13), người chơi bắt buộc phải cho viên bi di chuyển tại vị trí (0, 0) với chiều ban đầu là từ Trái->Phải.

Ở level 2 này, người chơi sẽ phải tìm vị trí ban đầu để đưa viên bi vào mê cùng, làm sao cho sau khi kết thúc trò chơi sẽ đạt được nhiều điểm nhất (vị trí này thuộc 4 cạnh của mê cung). Trong trường hợp có nhiều hơn 1 vị trí đạt được mức điểm cao nhất, ưu tiên vị trí đầu tiên tìm được theo quy tắc ngược chiều kim đồng hồ (bắt đầu từ vị trí [0,0]).

Cách di chuyển của Viên bi như đã quy định trong bài PROB13. Bạn hãy viết một chương trình tính toán vị trí mà người chơi có thể cho viên bi đi vào để đạt được điểm số cao nhất.

Input

Dòng đầu tiên là số testcase T của bài toán (1 <= T <= 100)

Dòng đầu tiên của mỗi testcase là số tự nhiên: N cho biết kích thước cạnh của mê cung (5 <= N <= 1000)

Mê cung được mô tả bởi N dòng tiếp theo, mỗi dòng N ký tự. Với ký tự '0' tức là vị trí không có góc cua, và viên bi tiếp tục di chuyển, ký tự '\' và '/' mô tả góc cua - viên bi phải di chuyển theo hướng quy định.

Output

Mỗi tescase được in trên 1 dòng với: bắt đầu bằng ký tự '#', tiếp theo là số thứ tự của testcase. tiếp theo là 1 dấu cách (khoảng trắng), và cuối cùng là kết quả của testcase đó. (Tham khảo Example Output để hiểu thêm)

Format của kết quả: x y result (tương ứng với vị trí [x, y] đạt được điểm cao nhất và result chính là giá trị điểm cao nhất đạt được)

Example

Input:
1
8
0\000000
00000\00
00000000
00000/00
000\00/0
0\\0\000
00000000
00000000
Output: #1 0 0 3