Nhóm hậu tố

Bạn được cung cấp một tập hợp gồm \(n\) xâu ký tự \(s_1, s_2, \ldots, s_n\).

Nhiệm vụ của bạn là tìm một tập con \(s_{i_1}, s_{i_2}, \ldots, s_{i_k}\) \((1 \leq i_1 < i_2 < \ldots < i_k \leq n)\) thoả mãn hai điều kiện sau:

1. Tồn tại một xâu \(t\) sao cho mỗi xâu trong tập con đã tìm được đều là hậu tố của xâu \(t\).

2. Số lượng xâu trong tập con phải là lớn nhất có thể.

Nhiệm vụ của bạn là in ra số lượng xâu trong tập con này.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 10^5)\) --- số lượng xâu trong tập hợp.
• \(n\) dòng tiếp theo, mỗi dòng chứa một xâu \(s_i\) --- xâu ký tự thứ \(i\). Mỗi xâu đều không rỗng và chỉ chứa các chữ cái Latin thường.
• Tổng độ dài của tất cả các xâu \(s_i\) không vượt quá \(10^5\).

Output

In ra một số nguyên duy nhất --- số lượng xâu lớn nhất có thể trong tập con thoả mãn điều kiện.

Example

6
bb
bb
b
aaa
aa
z

3

Scoring

Gọi \(S\) là tổng độ dài các xâu trong input.

• Có \(25\%\) số điểm có \(n \leq 8, S \leq 30\).
• Có \(25\%\) số điểm có \(n \leq 100, S \leq 1000\).
• Có \(25\%\) số điểm có \(n \leq 500\).
• \(25\%\) số điểm còn lại không có ràng buộc gì thêm.