English

Thanks to your help, Lam was able to access Phong's Wifi, and the hacking officially began.

Because the Y2K organization was carrying out a large-scale attack and Phong was forced to lead it, Phong invited Lam to stay at his house and have lunch with Phong's family, while Phong left, private room to work.

Lam is very happy about this, because he will not be "Vinasoy" by anyone during the hacking process. With the documents collected before, Lam knew that in Phong's campus there was a secret room - this place most likely contained the computer system of the Y2K organization.

Lam went to that room, but the challenge he faced this time was to authenticate the Fingerprint so he could open the door. It seems that this challenge is not simple, but with his agility, Lam managed to get Phong's fingerprint pattern on the cup of water when Phong brought water to invite him.

Fingerprint authentication system is identified by Lam as an optical machine system that is responsible for scanning fingerprint features and comparing with existing data, and this optical scanning head can be rotated in 4 directions. . Rotate right 90 degrees, rotate 180 degrees or rotate left 90 degrees (rotate right 270 degrees)

That is, Phong's fingerprint has been obtained, but Lam still cannot quickly open the door because he does not know which direction is the correct direction of the scanner. If you rotate the scanner and try it more than once, it will be detected by Phong's system. Therefore, Lam decided to attack the electronic circuit system to get information about the stored fingerprint pattern. Then, based on this sample and the existing fingerprint pattern, Lam will determine the direction of the scanner that needs to be rotated.

Fingerprint data is described by a square matrix, at position (i, j) will be the gray level feature of the fingerprint at that location (values from 0 to 255).

Because he only had time to attack the circuit system on the key, Lam sent the data including the performance of Fingerprint stored in the door system and the representation of Phong's Fingerprint that Lam had obtained for you. Please help Lam find the direction of rotation of the Fingerprint scanner.

Input

The first line indicates the number of test cases of the problem (T <= 100).

The first line of each test case is a natural number N indicating the size of the data representing Fingerprint (5 <= N <= 100)

Followed by 2*N lines, each line contains N integer values from 0 to 255 only know the value at position (i, j). In which, the first N lines are the fingerprint data stored in the door system and the following N lines are the fingerprint data that Lam has.

Output

Each test case is printed on one line with:

• Start with the character '#', followed by the number of the test case, followed by a space (space), and finally the number K indicating the direction to rotate.
• K takes values from 0 to 3 indicating the direction to rotate the scanner. Corresponds to 0: keep the same direction, 1: rotate right 90 degrees, 2: reverse rotation (rotate 180 degrees), 3: rotate left 90 degrees.

Example

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

Output:
#1 3

Vietnamese

Nhờ sự giúp sức của các bạn mà Lâm đã có thể truy cập vào Wifi nhà Phong, và việc hacking chính thức bắt đầu.

Do tổ chức Y2K đang thực hiện một cuộc tấn công với quy mô lớn và Phong bắt buộc phải chỉ huy, do đó Phong đã mời Lâm ở chơi ở khuôn viên nhà anh và đơi dùng bữa trưa cùng gia đình Phong, còn Phong thì đi vào phòng riêng để làm việc.

Lâm thì lại rất vui mừng vì điều này, vì anh sẽ không bị ai "Vinasoy" trong quá trình thực hiện hacking. Bằng những tài liệu thu tập được từ trước, Lâm biết rằng trong khuôn viên nhà Phong có 1 căn phòng bí mật - nơi đây rất có thể để chưa hệ thống máy tính của tổ chức Y2K.

Lâm tìm đến căn phòng đó, nhưng thử thách mà anh gặp phải lần này là phải xác thực Vân tay để có thể có thể mở cửa. Xem chừng thử thách này cũng không đơn giản, nhưng bằng sự nhanh nhẹn của mình Lâm đã có được mẫu Vân tay của Phong bám trên cốc nước khi mà Phong mang nước ra mời anh.

Hệ thống xác thực Vân tay được Lâm xác định là loại hệ thống máy quang học có nhiệm vụ quét các đặc trung trên vân tay và đối chiếu với dữ liệu đã tồn tại, và đầu quét quang học này có thể xoay được theo 4 hướng. Xoay phải 90 độ, xoay 180 độ hoặc xoay trái 90 độ (xoay phải 270 độ)

Tức là đã có được Vân tay của Phong rồi, nhưng Lâm vẫn không thể nhanh chóng mở cửa vì không biết hướng nào mới là hướng đúng của máy quét. Nếu xoay máy quét và thử quá 1 lần sẽ bị phát hiện bởi hệ thống của Phong. Do đó Lâm đã quyết định tấn công vào hệ thống mạch điện tử để lấy thông tin về mẫu vân tay đã được lưu trữ. Sau đó dựa vào mẫu này và mẫu vân tay đã có, Lâm sẽ xác định được chiều của máy quét cần xoay.

Dữ liệu vân tay được mô tả bằng một ma trận vuông, tại vị trí (i, j) sẽ là đặc mức xám của vân tay tại vị trí đó (giá trị từ 0->255).

Do chỉ kịp tấn công vào hệ thống mạch trên khóa nên Lâm đã gửi dữ liệu bao gốm biểu diễn của Vân tay lưu trữ trong hệ thống cửa và biểu diễn Vân tay của Phong mà Lâm đã thu được cho các bạn. Các bạn hãy giúp Lâm tìm chiều cần xoay của máy quét Vân tay các bạn nhé.

Input

Dòng đầu tiên cho biết số lượng Testcase của bài toán (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ủa dữ liệu biểu diễn Vân tay (5 <= N <= 100)

Tiếp theo là 2*N dòng, mỗi dòng bao gồm N giá trị nguyên từ 0->255 chi biết giá trị tại vị trí (i, j). Trong đó, N dòng đầu tiên là dữ liệu vân tay được lưu trữ trong hệ thống cửa và N dòng sau là dữ liệu vân tay mà Lâm có được.

Output

Mỗi testcase được in trên một dòng với:

 - Bắt đầu bằng ký tự '#', tiếp theo là số thứ tự của testcase, tiếp đến là một dấu cách (khoảng trắng), và cuối cùng là số K cho biết chiều cần xoay.

 - K nhận các giá trị từ 0->3 cho biết chiều cần xoay của máy quét. Tương ứng với 0: giữ nguyên chiều, 1: xoay phải 90 độ, 2: xoay ngược lại (xoay 180 độ), 3: xoay trái 90 độ

Example

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

Output:
#1 3