Một phần mềm quản lý tại công ty B-SOFT được một nhân viên phát hiện ra lỗi bảo mật rất thú vị. Phần mềm này phục vụ cho ~ n ~ nhân viên trong công ty, mỗi nhân viên có một tài khoản đi kèm với một mật khẩu để đăng nhập vào hệ thống nhưng trong một số trường hợp, nhân viên này có thể dùng mật khẩu của mình để đăng nhập vào tài khoản của nhân viên khác nếu chuỗi ký tự mật khẩu của nhân viên này chứa chuỗi con (các ký tự liên tiếp nhau) là mật khẩu của nhân viên kia. Giám đốc công ty muốn biết mật khẩu mỗi người có thể dùng để truy cập được bao nhiêu tài khoản của người khác.

Yêu cầu: Bạn hãy giúp Giám đốc công ty B-SOFT giải quyết bài toán trên.

Dữ liệu vào

• Dòng đầu ghi số nguyên dương ~ n ~ ~ (1 ≤ n ≤ 10000) ~.
• Dòng thứ ~ i ~ ~ ( i = 1…n) ~ trong ~ n ~ dòng tiếp theo, mỗi dòng ghi một xâu ký tự gồm các chữ cái thường trong bảng chữ cái tiếng Anh có độ dài không vượt quá 10.

Kết quả

Có ~ n ~ dòng, với dòng thứ ~ i ~ ~ (i = 1…n) ~ là số lượng tài khoản (không kể tài khoản của mình) mà người thứ ~ i ~ có thể đăng nhập được vào hệ thống bằng mật khẩu của mình.

Ràng buộc

• Có 50% số điểm với ~ n ≤ 1000 ~
• Có 50% số điểm với ~ 1000 ≤ n ≤10000 ~

Ví dụ:

Input 1

3
a
a
ab 

Output 1

1
1
2 

Input 2

5
mad
madam
da
m
a 

Output 2

2
4
1
0
0