Practice Permutations and Group theory with the exercise "Mathematics for big ears"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Statement

Goal

After having rung the bells https://www.codingame.com/training/medium/ring-the-bells (this puzzle is the second part of the bell themed puzzles), you will now learn how to find and count all the permutations that are generated by a set of permutations.
For example, if you have one permutation: p=(1 2 3), you can compose it with itself and you get q=(1 3 2). If you compose q and p, you get the null permutation e=() (the permutation that moves nothing). Here is the table of the operations below:

↱ | e | p | q
--+===+===+===
e ∥ e | p | q
--+---+---+---
p ∥ p | q | e
--+---+---+---
q ∥ q | e | p

This means that if you permute with p then with q (the yellow case in the table), you move nothing, that is e, the null permutation.
If you permute with p and again with p, you permute in fact with q (the blue case in the table).
In other words, there are only 3 distinct permutations that can be generated by p.

If you have the two permutations p=(1 2) and q=(1 3), you will be able to generate 6 distinct permutations: e=(), (1 2), (1 3), (2 3), (1 2 3) and (1 3 2). The output must be 6.
Each combination of these two permutations p and q is one of these six, even pqqqppqqp, that is pqp=(2 3).
The set of these six permutations is the third symmetric group (S3), the group of the bijections on a set of 3 elements.

The name of the tests and validators will help you debugging.

A bit of mathematics
A theorem by Cayley says that every finite group is isomorphic to a subgroup of a finite symmetric group.
You can find a copy of this subgroup in a finite symmetric group.
To be more precise, if a finite group G is generated by permutations of n elements, then there is a copy of G in the symmetric group on n elements.

Teddy bears
But why this poster image? Because it’s the cover image of Charlemagne Palestine’s album whose name is Music for big ears and it’s repetitive music for a bell carillon.

Some more mathematics, not needed to solve the puzzle
Here’s an explanation of the names of the groups, if you understand this paragraph, your ears are big.
* Cn are cyclic groups, the simplest groups you can build. They are the simple modular remainders when you calculate additions with modulus n.
* Sn are symmetric groups, for exemple S4 is the set of all the permutations you can imagine over 1 2 3 4.
* The Klein group is C2×C2, that is the addition over two coordinates with modulus 2: (0,0), (0,1), (1,0) and (1,1). Thus, (0,1)+(1,1)=(1,0) because 1+1=2=0 mod 2.
* Dn are dihedral groups, the groups of the isometries that keep the regular polygon with n vertices (eg symmetries and rotations).
* H is the group of quaternions (see the Quaternion multiplication by TheNinja medium puzzle about them), it’s a model of the rotations of a cube (see the CodinDice puzzle by BlitzProg).
* An is the subgroup of SN whose permutations are even, that means that the number of wrongly ordered pair of elements… is even.
* Fq is not a group but a field with q elements (like R or C but with a finite number of elements). You meet such things when you code self-correcting codes, for example. If q is prime, Fq is just Z with addition and multiplication but with modulus q.
* GL2(Fq) is the group of the inversible tranformations of the 2×2 matrices whose elements are in Fq.
SL2(Fq), PGL2(Fq) and PSL2(Fq) are explained below. The centre Z of a group G is its subgroup that commutes with everyone, eg for all g in Z, for all h in G, gh=hg. A quotient is when you identify some kind of elements who satisfy a condition.
* The group of the cube is the group of symmetries and rotations (and so on) that keeps a cube.
* The squares subgroups of the Rubik’s cube is the set of the moves such as R2U2D2. Here, we only look how it moves the vertices and the edges.
* The M12 Mathieu group is a sporadic group, one of the simple groups that can’t be classified in other great families.

Input

First line The number n of permutations
Next n lines A permutation

Output

The size of the subgroup.

Constraints

The final size is below 100,000.
You can assume that the given permutations are reduced (eg, what you can expect in the Ring the bells puzzle).

Example

Input

1
(1 2 3)

Output

Solve it

A higher resolution is required to access the IDE