[POI2006]Pal

给定 $n$ 个回文串 $s_1,s_2,\ldots,s_n$。求满足 $s_i+s_j$ 仍为回文串的有序二元组 $(i,j)$ 的数量，其中 $s_i+s_j$ 表示将字符串 $s_i$ 与 $s_j$ 拼接。

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行中，第 $i$ 行包含一个整数 $l_i$、一个空格以及一个长度为 $l_i$ 的小写英文字母串，分别表示字符串 $s_i$ 的长度和字符串内容。

不同的字符串可以相同。

输出格式

输出一个整数，表示满足条件的有序二元组 $(i,j)$ 的数量。

样例输入

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

样例输出

14

数据范围

• 所有输入字符串的总长度不超过 $2\times 10^6$；
• 每个输入字符串均为回文串，且仅由小写英文字母组成。

来源与许可

本题为 POI 2006 试题「Pal」，题面与测试数据整理自 BZOJ 1524。

样例 1

输入

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

输出

14