Саша очень любит строки и задачи на них. Особенно сильно в них он любит суффиксные структуры. Так как Саша очень любит сообщество TopForces, членом которого сам является, он хочет написать очередную статью под названием "О суффиксных деревьях, ч.37". Естественно, чтобы все поняли, о чём Саша пишет в своей статье, ему нужно снабдить её несколькими примерами. После очередного соревнования на TopForces Саша получил ранг "международный мажор" и теперь хочет соответствовать ему. Для этого Саша хочет из нескольких возможных строк для примера выбрать наиболее мажорные.

Разумеется, понятия Саши о мажорности строки основываются на уже упомянутых ранее суффиксных структурах, а именно — суффиксных деревьях. Чтобы посчитать мажорность строки, Саша производит следующий набор операций:

1. Строит сжатое суффиксное дерево для строки. Напомним, суффиксное дерево — бор, содержащий все суффиксы строки. Сжатое суффиксное дерево — тот же бор, в котором последовательно идущие рёбра соединены в одно, а на ребре записан не символ, а подстрока.
2. Для каждого ребра полученного дерева Саша считает число различных непустых подстрок на нём.

Мажорностью строки называется сумма посчитанных значений по всем рёбрам. К сожалению, Саша далеко не так хорош в суффиксных деревьях, как хочет, чтобы вы думали, и не может справиться с задачей самостоятельно. Помогите ему!

В первой строке входных данных записано целое число n (1 ≤ n ≤ 10⁵).

В следующих n строках находятся n слов, записанных малыми латинскими буквами — интересующие Сашу строки. Гарантируется, что суммарная длина всеx слов не превышает 10⁵ символов.

Выведите n чисел. i-ое число обозначает мажорность i-ой строки.

Сжатое суффиксное дерево для строки abaaa:

Рёбра: a, aa, baaa, baaa. Они имеют 1, 2, 7 и 7 различных непустых подстрок соответственно. Таким образом, ответ: 1 + 2 + 7 + 7 = 17.