One day in the magic world, the young wizard RoundDog was learning the compatibility of spells. After experimenting for a long time, he reached the conclusion that the compatibility of a spell collection can be measured by the number of distinct palindromes that are substrings of all the spells in the collection. He was so excited and planned to write a program to calculate the compatibility of any input spell collection.
However, RoundDog was busy participating the NowWizard Multi-Universe Training this week. He was too struggling during the competition and feels tired now.
Since RoundDog is not in the mood to finish the program now, could you help him?
输入格式
The first line contains a single integer kkk(1≤k≤5)(1 \leq k \leq 5)(1≤k≤5), indicating the number of spells in a spell collection.
In the following kkk lines, each line contains a spell SSS(1≤∣S∣≤300000)(1 \le |S| \le 300\,000)(1≤∣S∣≤300000), which is a string containing only lowercase English letters.
It is guaranteed that the total length of the spells does not exceed 300000300\,000300000.
输出格式
Output the compatibility of the input spell collection, which is the number of distinct palindromes that are substrings of all the spells in the collection.
输入样例
复制
3
abaca
abccaca
acabb
输出样例
复制
4
数据范围与提示
In the example, "a", "b", "c", "aca" are the four distinct palindromes that are substrings of all the input spells.