Cha mẹ Elliot nói tiếng Pháp và tiếng Anh với cậu ở nhà. Cậu đã nghe rất nhiều từ, nhưng không phải lúc nào cũng rõ từ nào thuộc ngôn ngữ nào!

Elliot biết một câu chắc chắn là tiếng Anh, một câu chắc chắn là tiếng Pháp, và một số câu khác có thể là tiếng Anh hoặc tiếng Pháp. Nếu một từ xuất hiện trong một câu tiếng Anh, nó phải là một từ tiếng Anh. Nếu một từ xuất hiện trong một câu tiếng Pháp, nó phải là một từ tiếng Pháp.

Xét tất cả những câu Elliot đã nghe, số từ ít nhất bắt buộc phải thuộc cả tiếng Anh lẫn tiếng Pháp là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(N\), sau đó là \(N\) dòng, mỗi dòng gồm một dãy "từ" cách nhau bởi dấu cách. Mỗi "từ" chỉ gồm các chữ thường a đến z.

Dòng đầu trong \(N\) dòng là một "câu" tiếng Anh, dòng thứ hai là một "câu" tiếng Pháp. Các dòng còn lại có thể là "câu" thuộc một trong hai ngôn ngữ. (Các "từ" và "câu" không được bảo đảm là hợp lệ trong bất kỳ ngôn ngữ thật nào.)

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(y\) là số từ ít nhất mà Elliot đã nghe và bắt buộc phải thuộc cả tiếng Anh lẫn tiếng Pháp.

Ràng buộc

• \(1 \le T \le 25\).
• Mỗi từ dài không quá 10 ký tự.
• Hai câu "đã biết" chứa không quá 1000 từ mỗi câu.
• Mỗi câu "chưa biết" chứa không quá 10 từ.

Phân nhóm

• Test Set 1 (Nhỏ): \(2 \le N \le 20\).
• Test Set 2 (Lớn): \(2 \le N \le 200\).

Đ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ụ

4
2
he loves to eat baguettes
il aime manger des baguettes
4
a b c d e
f g h i j
a b c i j
f g h d e
4
he drove into a cul de sac
elle a conduit sa voiture
il a conduit dans un cul de sac
il mange pendant que il conduit sa voiture
6
adieu joie de vivre je ne regrette rien
adieu joie de vivre je ne regrette rien
a b c d e
f g h i j
a b c i j
f g h d e

    ???+ success "Output"

        ```sample
Case #1: 1
Case #2: 4
Case #3: 3
Case #4: 8

??? "Giải thích"

    Trong Case #1, Elliot biết chắc câu đầu là tiếng Anh và câu thứ hai là tiếng Pháp nên không có gì mơ hồ; từ duy nhất bắt buộc thuộc cả hai ngôn ngữ là `baguettes`.

    Trong Case #2, hai câu cuối có thể lần lượt là: Anh-Anh, Anh-Pháp, Pháp-Anh, hoặc Pháp-Pháp. Khả năng thứ hai làm số từ chung của hai ngôn ngữ nhỏ nhất; tập đó là `d`, `e`, `i`, và `j`.

Nguồn

Google Code Jam 2015, Vòng 2, bài Bilingual.

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