Cũng như con người, những cô bò thường thích cảm thấy mình độc đáo theo một cách nào đó. Vì đàn bò của bác nông dân John đều thuộc cùng một giống và trông khá giống nhau, chúng muốn đo mức độ độc đáo qua tên của mình.

Tên của mỗi cô bò có một số xâu con. Ví dụ, “amy” có các xâu con {a, m, y, am, my, amy}, còn “tommy” có các xâu con sau: {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}.

Tên của một cô bò có một “hệ số độc đáo”, là số xâu con của tên đó không xuất hiện trong tên của bất kỳ cô bò nào khác. Ví dụ, nếu amy ở một mình trong đàn, hệ số độc đáo của cô là \(6\). Nếu tommy ở một mình trong đàn, hệ số độc đáo của cô là \(14\). Tuy nhiên, nếu cả hai ở cùng một đàn, hệ số độc đáo của amy là \(3\) và của tommy là \(11\).

Cho một đàn bò, hãy xác định hệ số độc đáo của từng cô bò.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1 \leq N \leq 10^5\)). Mỗi dòng trong \(N\) dòng tiếp theo chứa tên của một cô bò trong đàn. Mỗi tên chỉ gồm các chữ cái thường từ a đến z. Tổng độ dài của tất cả các tên không vượt quá \(10^5\).

Dữ liệu ra

In ra \(N\) số, mỗi số trên một dòng, mô tả hệ số độc đáo của từng cô bò.

Ví dụ

3
amy
tommy
bessie

3
11
19

Nguồn

USACO 2017 December Contest, Platinum — Standing Out from the Herd

Tác giả bài toán: Matt Fontaine.