COETEST5

Công ty X chuyên sản xuất các thiết bị đèn LED để cung cấp cho thị trường.

Công ty X nhận được một đơn hàng sản xuất một bảng thiết bị đèn LED bao gồm 3 màu: Đỏ, Lục và Lam.

Trong quá trình lắp các bóng đèn LED vào bảng mạch, nhân viên của công ty do buồn ngủ nên đã lắp nhầm các bóng đèn LED vào những vị trí không đúng. Do phải giao cho khách hàng gấp nên công ty X đã cử một nhân viên khác để lắp lại cho đúng vị trí trong thời gian ngắn nhất. Để làm được việc đó, nhân viên này sẽ phải tìm một cách lắp lại sao cho số bóng đèn LED thay đổi là ít nhất.

Ví dụ:

Bảng mạch đang bị xáo trộn như sau:

1 3 3 3 3 1 3 1 1 2 3 2 2 1 3 1 3 1 1

3 1 2 3 2 3 3 2 1 1 2 3 1 2 2 2 3 3 1

1 2 2 3 2 2 3 1 3 1 2 3 1 1 1 3 1 3 1

2 1 3 2 3 3 2 1 1 3 2 3 2 3 1 1 3 1 3

2 1 1 1 1 3 3 1 3 3 3 2 1 1 3 1 1 1 2

1 3 1 3 3 1 2 3 2 3 2 1 2 2 2 1 3 2 1

Trong đó:

• 1: quy ước là màu ĐỎ
• 2: quy ước là màu LỤC
• 3: quy ước là màu LAM

Bảng mạch trên có 6 hàng và 19 cột, tương ứng với 144 bóng đèn LED.

Khách hàng yêu cầu bảng mạch đèn LED được lắp đủ cả 3 màu và được sắp xếp thành 3 dải màu độc lập. Ví dụ bảng mạch sau sẽ là bảng mạch thỏa mãn yêu cầu khách hàng:

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3

Với 3 màu ĐỎ, LỤC và LAM, ta có thể có 6 tổ hợp màu như sau:

1. ĐỎ - LỤC - LAM
2. ĐỎ - LAM - LỤC
3. LỤC – ĐỎ - LAM
4. LỤC - LAM - ĐỎ
5. LAM - ĐỎ - LỤC
6. LAM - LỤC - ĐỎ

Cho thông tin về bảng mạch đang bị xáo trộn, hãy xác định xem với tổ hợp màu nào thì số bóng đèn LED cần thay là nhỏ nhất.

Ví dụ bảng mạch xáo trộn như trên:

1 3 3 3 3 1 3 1 1 2 3 2 2 1 3 1 3 1 1

3 1 2 3 2 3 3 2 1 1 2 3 1 2 2 2 3 3 1

1 2 2 3 2 2 3 1 3 1 2 3 1 1 1 3 1 3 1

2 1 3 2 3 3 2 1 1 3 2 3 2 3 1 1 3 1 3

2 1 1 1 1 3 3 1 3 3 3 2 1 1 3 1 1 1 2

1 3 1 3 3 1 2 3 2 3 2 1 2 2 2 1 3 2 1

Nếu áp dụng tổ hợp 1: ĐỎ - LỤC - LAM

• Cần thay đổi tất cả các số 2 và 3 của hai hàng đầu tiên thành số 1 => chúng ta cần thay đổi 25 bóng đèn.
• Cần thay đổi tất cả các số 1 và 3 của hai hàng tiếp theo thành số 2 => chúng ta cần thay đổi 28 bóng đèn.
• Cần thay đổi tất cả các số 1 và 2 của hai hàng cuối cùng thành số 3 => chúng ta cần thay đổi 26 bóng đèn.

Như vậy với tổ hợp 1 ta cần thay đổi tổng cộng: 25 + 28 + 26 = 79 bóng đèn.

Tương tự, ta cần xét với 5 tổ hợp màu còn lại xem tổ hợp nào cần thay ít bóng đèn nhất. Như ví dụ trên, ta áp dụng tổ hợp màu số 6 thì sẽ cần đổi 73 bóng đèn và đây là tổ hợp cần đổi ít bóng đèn nhất.

[Input]

Dòng đầu tiên là số test case T (T ≤ 50).

Mỗi test case được viết trên N + 1 dòng.

Dòng đầu tiên của mỗi test case bao gồm 2 số N (3 ≤ N < 200) và M (3 ≤ M ≤ 23) lần lượt là số hàng N và số cột M của bảng mạch. Dữ liệu luôn đảm bảo N chia hết cho 3.

N dòng tiếp theo thể hiện ma trận các bóng LED được lắp lộn xộn bao gồm các số 1, 2 và 3. Hai số cạnh nhau phân biệt nhau bởi một dấu cách.

[Output]

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

Mỗi test case in ra theo định dạng “#tc” với tc là số thứ tự của test case bắt đầu từ 1, sau đó là một dấu cách và tiếp theo là số bóng đèn cần đổi ít nhất.

Example

Input:
3
3 8
3 2 2 3 2 1 1 2
3 3 3 2 1 2 3 2
3 1 1 1 1 3 1 2
6 19
1 3 3 3 3 1 3 1 1 2 3 2 2 1 3 1 3 1 1
3 1 2 3 2 3 3 2 1 1 2 3 1 2 2 2 3 3 1
1 2 2 3 2 2 3 1 3 1 2 3 1 1 1 3 1 3 1
2 1 3 2 3 3 2 1 1 3 2 3 2 3 1 1 3 1 3
2 1 1 1 1 3 3 1 3 3 3 2 1 1 3 1 1 1 2
1 3 1 3 3 1 2 3 2 3 2 1 2 2 2 1 3 2 1
9 16
3 1 1 3 3 2 3 3 1 3 2 3 2 1 3 1
3 1 3 2 3 1 3 3 1 2 1 3 3 2 3 3
2 1 1 1 1 1 2 2 1 3 2 1 3 1 3 2
3 3 2 1 2 3 1 1 3 2 2 3 3 3 1 3
3 2 3 2 1 3 2 1 3 2 3 1 2 1 1 2
1 2 3 3 1 1 1 1 3 3 3 3 3 2 2 1
1 2 2 3 3 2 3 3 3 1 2 2 1 3 1 3
1 1 3 2 3 3 3 2 1 1 1 3 1 3 1 2
3 3 1 2 3 3 3 3 3 1 2 3 1 1 1 1

Output:
#1 11
#2 73
#3 93