ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1799. Sasha and swag strings

Time limit: 2.0 second
Memory limit: 256 MB
Sasha enjoys strings and problems on string theory. Especially he loves suffix structures. As Sasha loves TopForces community he is going to write an entry named “On suffix trees, part 37”. Surely, he wants everybody to understand what the article says, so he decided to decorate it with some nice examples. After a recent contest on TopForces, Sasha has achieved the rank “International swagger”, and now he wants to match it. To achieve this, Sasha wants to choose the swaggest strings among some given set.
Of course, Sasha’s concept of string swagness is based on suffix structures. To be precise, on suffix trees. To calculate the swagness of a string, Sasha performs the following actions:
  1. He constructs the compressed suffix tree of the string. Let us recall that a suffix tree is the trie built from all suffixes of the string. A compressed suffix tree is the same trie in which consecutive edges are merged. See the notes section for an example.
  2. On each edge of the compressed suffix tree, he counts the number of distinct non-empty substrings of the string which is written on the edge.
The swagness of the string is defined as the sum of the calculated values among all edges. Unfortunately, Sasha is not so good with the suffix trees as he wants you to think, and can’t handle the problem on his own. Help him!

Input

The first line contains an integer n (1 ≤ n ≤ 105).
Each of the next n lines contains a string. The i-th line contains a non-empty string si. Each string consists entirely of lowercase Latin letters. The total length of all strings si does not exceed 105.

Output

Print n integers, one per line. The i-th number must be the swagness of the string si.

Samples

inputoutput
3
umqra
umnik
merkurev
35
35
101
1
abaaa
17

Notes

Compressed suffix tree for string abaaa:
Problem illustration
Edges are a, aa, baaa and baaa. They have 1, 2, 7 and 7 distinct non-empty substrings, respectively. So, the answer is 1 + 2 + 7 + 7 = 17.
Problem Author: Alexander Kulkov
Problem Source: Petrozavodsk Summer 2015. Moscow IPT Contest