题目描述

小 $H$ 收集了一盒字符串碎片。每个碎片上写着一个由小写英文字母组成的非空字符串。

小 $H$ 发现，有些碎片其实是"同一块"：如果把一个字符串的首尾相接看成一个环，那么从一个位置开始顺时针读一圈，就可能读出另一个字符串。例如 abc、bca、cab 三者读出来的是同一个环，它们互为循环移位；而 abc 与 acb 则不是。

形式化地，称两个字符串 $x,y$ 同源，当且仅当 $|x|=|y|$，且存在一个整数 $k$（$0\le k<|x|$），使得 $y$ 等于把 $x$ 循环左移 $k$ 位后得到的字符串。

例如，长度为 $3$ 的字符串 abc 循环左移一位得到 bca，再左移一位得到 cab，于是这三个字符串两两同源；而 abc 与 cba 无论怎么移位都对不上，它们不同源。

现在给出 $n$ 个碎片上的字符串，请你求出有多少对碎片是同源的。由于答案可能较大，只需要输出对数即可。

碎片的数量可能很多，但所有碎片上的字符总数是有限的；同一个字符串可能出现多次，每次出现都算作一块独立的碎片。

小 $H$ 把碎片摊在桌面上，想先数一数有多少对碎片原本来自同一块。

输入格式

从标准输入读入数据。

输入的第一行包含一个正整数 $n$，表示碎片的数量。

接下来 $n$ 行，第 $i$ 行一个非空字符串 $s_i$，仅包含小写英文字母。

输入中的每个字符串独占一行，字符串内部不含空格，也不会出现空串；不同行上的字符串之间没有任何分隔符。

输出格式

输出到标准输出中。

输出一行一个整数，表示同源碎片的对数。

请只输出答案本身，不要输出任何多余的内容。

样例 1 输入

4
abc
bca
cab
ab

样例 1 输出

3

样例 1 解释

abc、bca、cab 三个字符串两两同源，共 $\binom{3}{2}=3$ 对；ab 长度为 $2$，与它们长度不同，不参与配对。

样例 2 输入

5
ab
ba
aab
aba
baa

样例 2 输出

4

样例 2 解释

ab 与 ba 同源，贡献 $1$ 对；aab、aba、baa 三者两两同源，贡献 $3$ 对。合计 $4$ 对。

样例 3

见选手目录下的 fragment/fragment3.in 与 fragment/fragment3.ans。

该样例满足测试点 $6\sim 8$ 的约束条件。

样例 4

见选手目录下的 fragment/fragment4.in 与 fragment/fragment4.ans。

该样例满足测试点 $9\sim 11$ 的约束条件。

样例 5

见选手目录下的 fragment/fragment5.in 与 fragment/fragment5.ans。

该样例满足测试点 $22\sim 25$ 的约束条件。

数据范围

设 $L=\sum_{i=1}^{n}|s_i|$。对于所有测试数据，保证：

• $1\le n\le 2\times 10^{5}$；
• $2\le L\le 2\times 10^{5}$；
• 每个 $s_i$ 均非空，且仅包含小写英文字母。

特殊性质 A：所有 $s_i$ 的长度相同。

特殊性质 B：所有 $s_i$ 仅包含字符 a 和 b。

特殊性质 C：所有 $s_i$ 长度不超过 $2$。

特殊性质 D：$n\le 2000$。

输入保证所有字符串均非空，且只包含小写英文字母。