Коровы Фермера Джона хотят измерить уникальность своих имён. Имя каждой коровы содержит некоторое количество подстрок. Например, "amy" имеет подстроки {a, m, y, am, my, amy}, а "tommy" имеет подстроки: {t, o, m, y, to, om, mm, my, tom, omm, mmy, tomm, ommy, tommy}.

Имя коровы имеет "фактор уникальности" - количество подстрок, которых нет у имён других коров. Например, если "amy" - единственная корова в стаде, её фактор уникальности равен 6. Если "tommy" - единственная корова в стаде, её фактор уникальности равен 1. Если в стаде 2 коровы "amy" и "tommy", то их факторы уникальности будут соответственно 3 и 11.

По заданному стаду коров определите фактор уникальности каждой коровы.

Входные данные

Первая строка содержит n (1 ≤ n ≤ 105). Каждая из следующих n строк содержит имя коровы в стаде. Каждое имя содержит только маленькие латинские буквы a-z. Общая длина всех имён не превысит 105.

Выходные данные

Выведите n чисел, по одному в строке, описывающие фактор уникальности каждой коровы.