Description

给定\(n\)个回文串，\(s_1,s_2,...,s_n\)。求有多少有序整数对 \((i,j)\) 使得\(s_is_j\) 仍为回文串。

Input

• 第一行一个整数\(n\)
• 接下来\(n\)行，每行先是一个整数\(w\)，表示这个字符串的长度；然后是一个空格；之后给出这个长度为\(w\)的字符串。保证\(w\ne 0\)。

Output

• 仅一个正整数，表示有序对的个数。

Sample

Input

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

Output

14

Hint

• 14个有序对中，6个为 \((i,i)\)，其他8个分别为：

• \((1,3),(1,5),(3,5),(2,6),(3,1),(5,1),(5,3),(6,2)\)

• \(m\)为总字符数。

• 对于20%的数据，\(n\le 100, m\le 500\)

• 对于40%的数据，\(n\le 5000, m\le 2000000\)

• 对于100%的数据，\(n\le 2000000, m\le 2000000\)