Cyclic Words

Interview

Time limit2sMemory limit128 MB

Summary

Count how many words are distinct once each is allowed to be read starting from any position around a circle.

Level: Easy3 of 10
Topics: String, Brute force, Hash map
Solved: No attempts yet

Problem

A cyclic word is made by writing a word around a circle. After choosing any position on the circle and reading clockwise, another linear word is obtained.

Two words are considered the same if one can be written in a circle and read from some starting position to obtain the other. For example, picture and turepic are the same word.

Given N words, count how many distinct words there are under this rule.

Input

The first line contains the number of words N.

Each of the next N lines contains one word. Every word consists only of lowercase English letters.

N is a positive integer no greater than 50, and each word has length at most 50.

Output

Print the number of distinct words.

Examples3

Example 1
Input
```
5
picture
turepic
icturep
word
ordw
```
Expected output
```
2
```
Example 2
Input
```
7
ast
ats
tas
tsa
sat
sta
ttt
```
Expected output
```
3
```
Example 3
Input
```
5
aaaa
aaa
aa
aaaa
aaaaa
```
Expected output
```
4
```