A jewelry-cataloging tool stores n bead-pattern strings, each of the same length. Two bead patterns belong to the same necklace group if one can be obtained from the other by rotating it cyclically (moving characters from the front to the back, e.g. abcd → bcda → cdab → dabc are all rotations of one another and thus the same necklace group).
Count the number of distinct necklace groups among the n given patterns.
Input format
Line 1: an integer n.
Lines 2 to n+1: one bead-pattern string per line. All n strings have the same length.
Output format
A single integer: the number of distinct necklace (rotation-equivalence) groups.
Constraints
- 1 ≤ n ≤ 1000
- Each pattern has length 1-40 and consists of lowercase English letters only. All
npatterns have the same length.