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  , indicating the number of spells in a spell collection.

In the following  lines, each line contains a spell  , which is a string containing only lowercase English letters.

It is guaranteed that the total length of the spells does not exceed .

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.