For two string A and B, we define that the similarity of these strings is the length of the prefix that is common to both. For example, the similarity of strings abc
and abd
is 2, while the similarity of strings aaa
and aaab
is 3.
Calculate the sum of similarities of a string S with each of its suffixes, including string as the first suffix.
Input Format:
The first line contains the number of T test cases. Each of the next T lines contains string each.
Output Format:
Display T output lines, each containing an integer that is for the corresponding test case.
Assumptions:
- 1