Description

作为大户人家，主人家里养了数量众多的喵。喵实在太多了，主人只能以颜色区分它们。主人发现自己的喵最多只有26种颜色，于是他用'a'...'z'这26个字母分别表示这26种颜色。注意：不同的喵颜色可能相同，但由于主人只以颜色区分喵，所以这两只喵对主人来说是相同的。喵们在睡觉的时候喜欢排成一个圆圈，主人想知道喵们睡觉的时候有多少种排列方式，所以他记录下了n天喵们睡觉时的排列。由于喵排成了一个圆圈，所以排列abcde和排列cdeab是相同的（它们可以组成相同的圆圈）。现在请你帮忙计算，在这n天里，喵们共出现了多少种不同的排列方式。

Format

Input

有多组数据。对每组数据，第一行是一个整数n，表示主人共记录了n天。接下来n行长度相同的由小写字母组成的非空字符串序列，表示喵睡觉时的排列。
数据组数<=100，1<=n<=10000，喵的数量不超过100.
读到文件末程序结束

Output

对每组数据，输出一个整数，占一行，表示这n个排列里有多少种不同的排列。

Sample 1

Input

5
aacde
acdea
cdeaa
deaac
eaacd
3
ffffff
gggggg
hhhhhh

Output

1
3

Limitation

1s, 262144KiB for each test case.

Hint

对30%的数据，1<=单个字符串长度<=10，1<=n<=1000;
对50%的数据，1<=单个字符串长度<=100，1<=n<=1000;
对100%的数据，1<=数据组数<=10，1<=单个字符串长度<=100，1<=n<=10000;

Source

HDU