COETEST5

Mẫu hình khóa là một loại khóa màn hình điện thoại rất phổ biến hiện nay, bằng cách nối các điểm trên màn hình bằng một nét duy nhất để tạo ra một mẫu hình mở khóa.

Hình dưới đây mô tả về Mẫu hình khóa gồm 9 chấm tròn xếp đều trên lưới ô vuông có kích thước 3 x 3.

Quy tắc nối các điểm để tạo ra mẫu hình như sau:

1.      Mẫu hình phải chứa ít nhất 4 điểm.

2.      Mỗi điểm chỉ được sử dụng tối đa một lần trong mẫu hình.

3.      Hai điểm có thể được kết nối với nhau nếu đoạn thẳng nối hau điểm đó không đi qua bất kỳ điểm nào khác, hoặc nếu đoạn thẳng đấy đi qua một điểm đã tồn tại trong mẫu hình.

Cho thông tin về mẫu hình, hãy kiểm tra xem mẫu hình đó có tuân thủ theo các quy tắc bên trên hay không?

[Ví dụ]

Để đơn giản, các điểm sẽ được đánh số từ 1 đến 9 như hình dưới đây.

• Hình 1 mô tả mẫu hình đi qua các điểm theo thứ tự 7→4→1→5→3→6→9.
• Hình 2 mô tả mẫu hình đi qua các điểm theo thứ tự 1→5→9→6→3→7.

o   Đoạn thẳng nối hai điểm 3 và 7 phải đi qua 5, tuy nhiên tại thời điểm nối hai điểm 3 và 7 thì điểm 5 đã tồn tại trong mẫu hình nên việc nối hai điểm 3 và 7 là hợp lệ.

• Hình 3 mô tả mẫu hình đi qua các điểm theo thứ tự 1→6→8→7→9.

o   Tương tự ví dụ trong hình 2, đoạn thẳng nối hai điểm 7 và 9 phải đi qua điểm 8, tuy nhiên điểm 8 đã tồn tại trong mẫu hình nên mẫu hình 16879 cũng hợp lệ.

• Hình 4 mô tả mẫu hình đi qua các điểm 9→7→8→6→1.

o   Mẫu hình này không hợp lệ, vì đoạn thẳng nối hai điểm 9 và 7 đi qua điểm 8, tuy nhiên tại thời điểm nối, điểm 8 chưa tồn tại trong mẫu hình (vi phạm quy tắc số 3).

[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:

Mỗi test case được cho trên N + 1 dòng, trong đó:

Dòng đầu tiên là số N nằm trong đoạn [1, 50] mô tả số lượng mẫu hình cần kiểm tra trong test case đó.

Trong N dòng tiếp theo, mỗi dòng là một xâu chỉ gồm chứa các ký tự số từ 1 đến 9, có độ dài L nằm trong đoạn [1,9].

[Output]

Đưa ra output trên T dòng tương tứ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 gồm một chuỗi số gồm N ký tự như sau:

• Nếu mẫu hình hợp lệ, in ra ký tự tương ứng là “0”.
• Nếu mẫu hình vi phạm duy nhất quy tắc số 1, in ra ký tự tương ứng là “1”.
• Nếu mẫu hình vi phạm duy nhất quy tắc số 2, in ra ký tự tương ứng là “2”.
• Nếu mẫu hình vi phạm duy nhất quy tắc số 3, in ra ký tự tương ứng là “3”.
• Nếu mẫu hình vi phạm nhiều hơn một quy tắc, in ra ký tự tương ứng là “4”.

Các ký tự viết liền không chứa dấu cách. 

Example

Input:
5
5
1
26879345
2
163458279
694389271
2
762381
25731864
5
715286
2948317
4152368
41629
27538694
7
159436782
34526719
128347956
153649
16529487
24963857
2631

Output:
#1 0
#2 02
#3 00
#4 30000
#5 0030000