Standing Out from the Herd

Just like humans, cows often appreciate feeling they are unique in some way. Since Farmer John's cows all come from the same breed and look quite similar, they want to measure uniqueness in their names.

Each cow's name has some number of substrings. For example, "amy" has substrings {a, m, y, am, my, amy}, and "tommy" would have the following substrings: {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}.

A cow name has a "uniqueness factor" which is the number of substrings of that name not shared with any other cow. For example, If amy was in a herd by herself, her uniqueness factor would be 6. If tommy was in a herd by himself, his uniqueness factor would be 14. If they were in a herd together, however, amy's uniqueness factor would be 3 and tommy's would be 11.

Given a herd of cows, please determine each cow's uniqueness factor.

Problem credits: Matt Fontaine

Input

The first line of input will contain N (1 \le N \le 10^5). The following N lines will each contain the name of a cow in the herd. Each name will contain only lowercase characters a-z. The total length of all names will not exceed 10^5.

Output

Output N numbers, one per line, describing the uniqueness factor of each cow.

Example

Source

USACO 2017 December Platinum

#4033

Standing Out from the Herd 2s 512MB

Problems

Input

Output

Example

Source

#4033 upload - done - how_to_reg -

Standing Out from the Herd timer 2s memory 512MB

Problems text_fields

Input

Output

Example

Source

Backlinks Official problem sets only

#4033

Standing Out from the Herd 2s 512MB

Problems