COETEST5

Trò chơi sudoku là một trò chơi điền các số từ 1 đến 9 vào ma trận 9x9 sao cho c ác số không bị trùng lặp trên hàng ngang, hàng dọc và ma trận con 3x3. Cho 1 ma trận 9x9 tượng trưng cho 1 đề Sudoku, trong đó vị trí của các dấu “.” là vị trí chưa được giải.
Viết một chương trình kiểm tra tính đúng đắn của một đề sudoku. Đề sudoku hợp lệ là không có 2 số trùng nhau trên cùng 1 hàng, 1 cột và ma trận con 3x3. Nếu h ợp lệ in ra số 1, không hợp lệ in ra số 0.

Input

Dòng đầu tiên của input là số test case, mỗi test case sẽ được viết trên 9 dòng.

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), tiếp theo là kết quả.

Example

Input:
2
...14..2.
..6......
.........
..1......
.67.....9
......81.
.3......6
.....7...
...5...7.
....2..9.
....6....
71..75...
.7.......
....83...
..8..7.6.
.....2...
.1.2.....
.2..3....

Output:
#1 1
#2 0