[AdditionalFile5508.zip](file://AdditionalFile5508.zip?type=additional_file)

#5508. 「POI2006 R3」回文串 Palindromes

标签: 传统 | 时间限制: 1500 ms | 内存限制: 128 MiB |

题目描述

题目译自 XIII OI Olimpiada Informatyczna – III etap Palindromy

小 Jasio 喜欢玩文字游戏。他挑选了 $n$ 个回文串（回文串指正读和反读都完全相同的词，例如 ala、anna 或 kajak），然后用它们组成了所有可能的 $n^2$ 个有序对，并将这些有序对中的回文串拼接成单个的字符串。最后，Jasio 统计了这样得到的新字符串中有多少个是回文串。但他不确定自己有没有算错，所以请你来重复同样的操作并告诉他结果。请编写一个程序来替你完成这项任务。

请编写一个程序，实现以下功能：

• 从标准输入读取 Jasio 提供给你的回文串，
• 计算出由读取的回文串有序对拼接而成的新字符串中，有多少个是回文串，
• 将结果输出到标准输出。

输入格式

输入的第一行包含一个整数 $n$ $(n \ge 2)$，表示 Jasio 提供的回文串数量。

接下来的 $n$ 行是各个回文串的描述。第 $i+1$ 行包含一个正整数 $a_i$，表示第 $i$ 个回文串的长度，以及一个由 $a_i$ 个英文小写字母组成的该回文串。数字 $a_i$ 和回文串之间由单个空格隔开。不同行中给出的回文串是互不相同的。所有回文串的总长度不超过 $2000000$。

输出格式

输出的第一行且仅一行应包含一个整数：所有能够拼接成新回文串的有序回文串对的数量。

样例

输入

6
2 aa
3 aba
3 aaa
6 abaaba
5 aaaaa
4 abba

输出

14