Truyền thuyết đô thị kể rằng nếu bạn truy cập trang chủ Google và tìm kiếm từ khóa "Google", vũ trụ sẽ nổ tung. Chúng tôi có một bí mật muốn chia sẻ... Điều đó là có thật! Làm ơn đừng thử, hoặc kể cho bất kỳ ai. Được rồi, có lẽ không phải vậy. Chúng tôi chỉ đùa thôi.

Nhưng điều tương tự không đúng với một vũ trụ xa xôi nào đó. Ở vũ trụ đó, nếu bạn tìm kiếm trên bất kỳ công cụ tìm kiếm nào bằng chính tên của công cụ tìm kiếm đó, vũ trụ sẽ thực sự nổ tung!

Để chống lại điều này, mọi người đã nghĩ ra một giải pháp thú vị. Tất cả các truy vấn được tập hợp lại với nhau. Chúng được chuyển đến một hệ thống trung tâm để quyết định truy vấn nào sẽ được gửi đến công cụ tìm kiếm nào. Hệ thống trung tâm gửi một loạt các truy vấn đến một công cụ tìm kiếm và có thể chuyển sang một công cụ khác bất cứ lúc nào. Các truy vấn phải được xử lý theo đúng thứ tự mà chúng được nhận. Hệ thống trung tâm tuyệt đối không được gửi một truy vấn đến một công cụ tìm kiếm có tên trùng với truy vấn đó. Để giảm chi phí, số lần chuyển đổi giữa các công cụ tìm kiếm phải được tối thiểu hóa.

Nhiệm vụ của bạn là cho chúng tôi biết hệ thống trung tâm sẽ phải chuyển đổi giữa các công cụ tìm kiếm bao nhiêu lần, giả sử rằng chúng ta lập trình nó một cách tối ưu.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ test, \(N\). \(N\) bộ test tiếp theo sẽ lần lượt xuất hiện.

Mỗi bộ test bắt đầu bằng số \(S\) -- số lượng công cụ tìm kiếm. \(S\) dòng tiếp theo, mỗi dòng chứa tên của một công cụ tìm kiếm. Mỗi tên công cụ tìm kiếm dài không quá 100 ký tự và chỉ chứa các chữ cái in hoa, chữ cái in thường, khoảng trắng và chữ số. Sẽ không có hai công cụ tìm kiếm nào có cùng tên.

Dòng tiếp theo chứa một số \(Q\) -- số lượng truy vấn đến. \(Q\) dòng tiếp theo, mỗi dòng chứa một truy vấn. Mỗi truy vấn sẽ là tên của một công cụ tìm kiếm có trong bộ test đó.

Dữ liệu ra

Với mỗi bộ test, bạn nên xuất ra:

Case #X: Y

trong đó \(X\) là số thứ tự của bộ test và \(Y\) là số lần chuyển đổi công cụ tìm kiếm.

Không tính lựa chọn công cụ tìm kiếm ban đầu là một lần chuyển đổi.

Ràng buộc

• \(0 < N \le 20\)

Phân nhóm

• Small dataset (Test set 1 - Visible): \(2 \le S \le 10\), \(0 \le Q \le 100\).
• Large dataset (Test set 2 - Hidden): \(2 \le S \le 100\), \(0 \le Q \le 1000\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
5
Yeehaw
NSM
Dont Ask
B9
Googol
10
Yeehaw
Yeehaw
Googol
B9
Googol
NSM
B9
NSM
Dont Ask
Googol
5
Yeehaw
NSM
Dont Ask
B9
Googol
7
Googol
Dont Ask
NSM
NSM
Yeehaw
Yeehaw
Googol

Case #1: 1
Case #2: 0

Nguồn

Google Code Jam 2008, Vòng loại, bài Saving the Universe.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.