COETEST5

Problem :

Trong một cuộc thi Robocon, 2 Robot sẽ được đặt vào 2 vị trí bất kỳ khác nhau trong một trận vuông A.

Ma trận vuông A kích thước NxN chứa các số nguyên D (1 <= D <= 4) là hướng đi tiếp theo của các robot ở vị trí đó (1 : Lên, 2 : Phải, 3 : Xuống, 4 : Trái)

Ở các vị trí biên sẽ không có giá trị nào làm robot đi ra khỏi ma trận.

Sẽ có S lượt đi cho mỗi robot. Vị trí của robot ở lượt đi tiếp theo sẽ phụ thuộc vào giá trị ở vị trí hiện tại của robot đó.

[Example]

- Vị trí hiện tại của robot (4, 1).

- Sau lượt đi thứ nhất, robot di chuyen sang ô (4, 2) do giá trị của ô (4,1) là 2.

- Sau lượt đi thứ hai, robot có vị trí là (5,2) do giá trị của ô (4,2) là 3.

Ở mỗi lượt đi, sẽ có khả năng 2 robot sẽ gặp nhau và va chạm với nhau. Có 2 trường hợp được tính là va chạm như sau :

Trường hợp 1 : bưới đi tiếp theo của 2 robot vào cùng 1 vị trí (khác với 2 vị trí hiện tại)

Trường hợp 2 : Sau khi di chuyển thì hai robot sẽ hoán đổi vị trí cho nhau.

Example :

Giả sử cho N =3 và S = 3 và ma trận bước đi của robot như sau:

+ nếu chọn vị trí của 2 robot lần lượt  (0, 0) và (0,1) thì 2 robot sẽ bị va nhau sau lần di chuyển thứ 2.

+ nếu chọn vị trí của 2 robot lần lượt (0,0) và (1,0) thì 2 robot sẽ không va chạm nhau sau 3 bước đi.

Chú ý: Các Robot là như nhau. Vậy nên khi ta đổi vị trí của 2 robot cho nhau thì vẫn được tính là 1 cặp vị trí.

Input:

Dòng đầu tiên là số lượng test case T (T <= 50). Thông tin về mỗi test case như sau :

Dòng đầu tiên là 2 số N (3<= N <= 100) và S (3 <= S <= 100)) tương ứng là kích thước mảng và số lượt đi của mỗi robot.

Trong N dòng tiếp theo, mỗi dòng thứ i gồm N số nguyên dương D(1 <= D <= 4) tương ứng là hướng đi tiếp theo của robot tại vị trí đó.

Output:

Đưa ra output trên T dòng tương ứng với T test case.

Mỗi test case in ra "#tc" với tc là số thứ tự của test case, đánh số bắt đầu từ 1, tiếp theo là một dấu cách và kết quả tương ứng của test case đó.

Kết quả in ra số cặp vị trí mà hai robot không va chạm nhau.

Example

Input:
4
4 9
2 3 4 4 
2 4 1 3 
3 1 1 4 
2 2 2 1 
7 22
3 2 3 3 2 3 3 
1 3 4 3 1 3 1 
2 1 1 2 2 1 3 
1 4 4 4 1 3 1 
1 2 1 3 1 4 3 
2 1 3 4 1 3 1 
2 4 4 1 4 1 1 
4 29
2 2 4 3 
3 3 4 3 
2 3 1 1 
1 1 1 1 
5 19
2 4 3 2 3 
1 4 3 3 3 
3 3 1 4 1 
3 3 1 4 1 
2 1 4 4 4

Output:
#1 22
#2 930
#3 75
#4 227