反转相同

题目描述

有 $N$ 根木棒,每根木棒上粘着若干个球。每个球上写有一个小写英文字母。

对于每个 $i = 1, 2, \ldots, N$,粘在第 $i$ 根木棒上的球上的字母用字符串 $S_i$ 表示。 具体来说,粘在第 $i$ 根木棒上的球的数量等于字符串 $S_i$ 的长度 $|S_i|$,且 $S_i$ 是从木棒的一端开始看时球上字母的序列。

当一根木棒从一端开始的球上字母序列与另一根木棒从一端开始的序列相等时,这两根木棒被视为相同。 更正式地说,对于 $1$ 到 $N$ 之间的整数 $i, j$,第 $i$ 根木棒与第 $j$ 根木棒被视为相同,当且仅当 $S_i$ 等于 $S_j$ 或其反转。

输出 $N$ 根木棒中不同木棒的数量。

输入格式

输入按以下格式从标准输入给出:

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出答案。

样例

6
a
abc
de
cba
de
abc

3

$S_2$ = abc 与 $S_4$ = cba 的反转相等,因此第 2 根和第 4 根木棒被视为相同。

$S_2$ = abc 与 $S_6$ = abc 相等,因此第 2 根和第 6 根木棒被视为相同。

$S_3$ = de 与 $S_5$ = de 相等,因此第 3 根和第 5 根木棒被视为相同。

因此,6 根木棒中共有 3 种不同的木棒:第 1 根、第 2 根(与第 4、6 根相同)、第 3 根(与第 5 根相同)。

数据范围

• $N$ 是整数。
• $2 \le N \le 2 \times 10^5$
• $S_i$ 是由小写英文字母组成的字符串。
• $|S_i| \ge 1$
• $\sum_{i=1}^{N} |S_i| \le 2 \times 10^5$