Just like humans, cows often enjoy feeling unique in some way. Since all of Farmer John's cows come from the same breed and look quite similar, they want to measure their uniqueness based on their names.
Each cow's name has a certain number of substrings. For example, has the substrings {, , , , , }, while has the following substrings: {, , , , , , , , , , , , , }.
A cow's name has a "uniqueness factor," defined as the number of substrings of that name that do not occur in any other cow's name. For example, if were the only cow in the herd, her uniqueness factor would be . If were the only cow in the herd, his uniqueness factor would be . If they were in the same herd, however, 's uniqueness factor would be , while 's would be .
Given a herd of cows, determine the uniqueness factor of each cow.
The first line contains an integer n~(1 \le n \le 10^5). The following lines each contain the name of a cow in the herd. Each name consists only of lowercase letters '' - ''. The total length of all cow names does not exceed 10^5.
Print numbers, one per line, representing the uniqueness factor of each cow.
Example 1