COETEST5

Cho ma trận kích thước n * n (n <=100) gồm các ký tự 0 và 1 , Đếm số lượng các chữ cái xuất hiện trong ma trận n*n. các chữ cách nhau và luôn có nghĩa.

Mỗi chữ nằm trong 1 block 3x3 và được bao bọc tối thiểu bởi 1 dãy số 0. Các chữ có thể xoay 90-180-270 độ

Các chữ cái mẫu sẽ giống với ma trân 3x3 dưới đây

ví dụ n = 3

TH1: chữ L

100

100

111

Th2: chữ T

111

010

010

TH3: chữ U

101

101

010

TH4: chữ H

101

111

101

4 trường hợp trên lần lượt là:

+ 1 chữ L,0 chữ T,0 chữ U, 0 chữ H

+0 chữ L ,1 chữ T,0 chữ U, 0 chữ H

+0 chữ L,0 chữ T,1 chữ U,  0 chữ H

+0 chữ L,0 chữ T,0 chữ U, 1 chữ H

Lưu ý: các dãy số 0 có thể dùng chung nhau để tách biệt các chữ được. Tức là, 2 chữ ở cạnh nhau có thể có 1 dãy số 0 làm viền chung được

Input

Dòng đầu tiên của input chứa số test case T (T <= 50)

Mỗi test case được biểu diễn trên N+1 dòng

dòng 1: kích thước ma trận vuông N x N (N <= 100)

N dòng tiếp theo thể hiện các giá trị trong mảng 2 chiều N x N

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 bao gồm 4 chữ số: số lượng chữ H, số lượng chữ T, số lượng chữ L, số lượng chữ U. Các số phân biệt nhau bởi dấu cách

Example

Input:
3 
10 10
1 0 0 0 0 0 1 1 0 0 
1 0 0 0 0 0 0 0 0 0 
1 1 1 0 0 0 1 0 1 0 
0 0 0 0 0 0 1 0 1 0 
1 1 1 0 0 0 0 1 0 0 
0 1 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 1 1 1 
0 1 1 1 0 0 0 0 0 0 
10 10
1 1 1 0 1 0 0 0 0 0 
0 0 0 0 1 0 0 0 0 0 
1 1 1 0 1 1 1 0 0 0 
0 1 0 0 0 0 0 0 0 0 
1 1 1 0 1 1 1 0 0 0 
0 0 0 0 0 0 1 0 0 0 
0 0 0 0 0 0 1 0 0 0 
0 0 0 1 0 0 0 0 1 0 
0 0 1 0 1 0 0 0 1 0 
0 0 1 0 1 0 0 0 1 0 
10 10
0 0 0 1 0 0 0 0 0 0 
0 1 0 0 0 0 0 0 0 0 
1 0 1 0 1 1 0 0 0 0 
1 0 1 0 0 0 1 0 0 0 
0 0 0 0 1 1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 1 1 1 
1 1 1 0 0 0 0 1 0 0 
0 0 1 0 0 0 0 1 0 0 

Output:
#1 0 1 2 1
#2 1 0 2 1
#3 0 1 1 2