Một cây tiền tố (còn gọi là trie) là một cấu trúc dữ liệu dùng để biểu diễn tất cả các tiền tố của các từ trong một tập hợp từ hữu hạn theo cách sau:

• Mỗi cạnh của cây được ký hiệu bằng một chữ cái latin.
• Gốc (root) của cây thể hiện một tiền tố rỗng (empty prefix).
• Trừ đỉnh gốc, mỗi đỉnh còn lại của cây tượng trưng cho một tiền tố khác rỗng. Cụ thể, mỗi đỉnh tượng trưng cho tiền tố nhận được bằng cách ghép lần lượt tất cả các chữ cái trên các cạnh thuộc đường đi từ đỉnh gốc tới đỉnh đó.
• Không bao giờ tồn tại hai cạnh cùng đi ra từ một đỉnh mà chúng được ký hiệu bằng cùng một chữ cái.

Hình dưới đây minh họa một cây tiền tố của tập hợp các từ A, to, tea, ted, ten, i, in và inn.

Cho trước một tập hợp gồm \(N\) từ, bạn hãy xác định số đỉnh tối thiểu cần có của một cây tiền tố để nó có thể biểu diễn được tập hợp từ này, biết rằng với mỗi từ chúng ta có thể hoán vị các chữ cái của nó theo một trật tự tùy ý.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1\leq N\leq 16)\).

• \(N\) dòng tiếp theo mô tả các từ trong tập hợp, mỗi dòng chứa một từ đơn chỉ gồm các chữ cái latin in thường.

• Tổng độ dài của tất cả các từ không vượt quá \(1,000,000\).

Output

• Một số nguyên duy nhất là số đỉnh tối thiểu tìm được.

Example

3
a
ab
abc

4

3
a
ab
c

4

4
baab
abab
aabb
bbaa

5