To read the problem statement in English, choose the language using the flag on the navigation bar.

Lộc thích màu lam đậm, nên lần đầu tiên mà Lộc đăng kí tài khoản trên một trang Online Judge giấu tên, Lộc đã quyết định sử dụng nickname darkcyan. Buồn thay, nickname này đã được sử dụng. Vì nickname bị trùng lặp, hệ thống có gợi ý Lộc sử dụng các nickname khác như darkcyan_no1, darkcyan_pro và darkcyan_vip, tuy nhiên Lộc không thích các nickname đó. Sau một hồi đắn đo suy nghĩ, nickname mà Lộc chọn là darkkcyan, rất gần với nickname ban đầu, nhưng kí tự k được nhân đôi lên. Và thật may mắn là nickname này chưa tồn tại! Nickname này đã được Lộc sử dụng cho hệ thống này cũng như trên nhiều nền tảng khác nhau.

Lộc nhận thấy rằng việc thay đổi nickname như thế thật là thú vị, và có thể áp dụng ý tưởng này để tạo ra một hệ thống gợi ý nickname hoàn toàn mới! Cụ thể, với một nickname được biểu diễn bởi xâu gồm ~k~ kí tự ~t_1 t_2 \ldots t_k~, hệ thống có thể biến đổi nickname sử dụng theo tác sau một số lần (có thể là 0 lần):

• Hệ thống chọn ra một số nguyên ~i~ (~1 \le i \le k~) tùy ý, và chèn một kí tự ~t_i~ vào ngay sau vị trí ~i~. Kí tự mới có chỉ số là ~i + 1~ và các kí tự sau đó có chỉ số được tăng lên một. Độ dài của nickname mới sẽ là ~k + 1~.

Ví dụ, với nickname darkcyan, với một thao tác có thể tạo ra xâu darkkcyan, ddarkcyan, và darkcyann, và với ba thao tác có thể tạo ra xâu ddaarrkcyan, darkkkkcyan hoặc ddarkkcyann.

Để đảm bảo độ tối ưu, hệ thống cần biến đổi nickname với số thao tác biến đổi ít nhất, sao cho nickname sau khi biến đổi chưa tồn tại trong hệ thông, để gợi ý cho người dùng.

Lộc nghĩ rằng sẽ thật đáng tiếc nếu như không có hệ thống gợi ý nickname trùng lặp nào sử dụng ý tưởng này. Do đó Lộc quyết định áp dụng luôn hệ thống gợi ý nickname này cho mạng xã hội Virtual Network for Online Intercommunication (VNOI) mà mình đang tham gia phát triển. Hiện tại trên mạng xã hội VNOI đã có ~n~ người dùng, và người dùng thứ ~i~ có nickname là xâu kí tự ~S_i~. Lộc muốn biết rằng, với mỗi nickname ~S_i~, nếu nếu như có một người dùng mới khi đăng kí hệ thống sử dụng nickname trùng với nickname này, vậy cần ít nhất bao nhiêu thao tác biến đổi nickname này để tạo ra một nickname chưa được sử dụng trên VNOI. Vì Lộc vẫn đang bận phát triển thành phần khác của hệ thống, nên Lộc muốn nhờ các bạn giải quyết bài toán này.

Cho danh sách nickname của ~n~ người dùng trên hệ thống, yêu cầu với mỗi nickname ~S_i~, cần in ra số lượng thao tác biến đổi ít nhất để biến đổi nickname ~S_i~ thành một nickname mới chưa tồn tại trên hệ thống.

Input

Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 10^6~) là số lượng người dùng mạng xã hội VNOI.

Dòng thứ ~i~ trong ~n~ dòng tiếp theo chứa xâu ~S_i~ (~1 \le |S_i| \le 10^6~, ~S_i~ chỉ chứa các kí tự tiếng Anh in thường) là nickname của người dùng thứ ~i~ trên hệ thống.

Dữ liệu đảm bảo tổng độ dài của tất cả các nickname trên hệ thống không quá ~10^6~ và không tồn tại hai nickname nào giống nhau.

Output

In ra ~n~ dòng. Dòng thứ ~i~ là số lượng thao tác biến đổi ít nhất để biến đổi nickname ~S_i~ thành một nickname mới chưa tồn tại trên hệ thống.

Scoring

• Subtask 1, tương ứng với ~55~ điểm, các kí tự trong cùng một nickname là giống nhau.

• Subtask 2, tương ứng với ~75~ điểm, không có ràng buộc gì thêm.

Tộng cộng bài toán có ~130~ điểm.

Sample Input 1

3
aaa
a
aa

Sample Output 1

1
3
2

Sample Input 2

3
ab
aab
abb

Sample Output 2

2
1
1