Abelian Groups

In the country of Berlandia, in the city called $N$, there is a unique tradition. If a girl wants to marry a young man, and he does not intend to give her all possible necklaces made of six beads, then she must present him with a new abelian group of order $N$ each day. Only after all possible abelian groups have been presented will the young man agree to give her a necklace every day, and eventually, they will marry. If two abelian groups are isomorphic, they are considered the same and only one of them must be presented. Athena, a girl who fell in love with a very busy programmer named Petya, wants to know how many days she needs to give him abelian groups before he agrees to give her necklaces.

Let us recall the main concepts and facts regarding abelian groups.

An abelian group is a pair G=(A,*), where $A$ is a set, and $\ast$ is a binary operation on $A$, that is, for any two elements $a$ and $b$ from $A$, the result a*b is also an element of $A$. The following properties, called the axioms of abelian groups, must be satisfied:

(i) Associativity: For any $a$, $b$, $c$ in $A$, the equality (a*b)*c = a*(b*c) holds.

(ii) There exists an element $e$ in $A$ such that for any $a$ in $A$, a*e = e*a = a.

(iii) For any $a$ in $A$, there exists $b$ in $A$ such that a*b = b*a = e.

(iv) Commutativity: For any $a,b$ in $A$, the equality a*b = b*a holds.

An important example of an abelian group is the cyclic group of order $n$: the set of numbers from $0$ to n-1 with addition modulo $n$. This group is denoted by Z_n.

The direct sum of two abelian groups G=(A,*) and H=(B, \cdot) is the pair GH = (C, \times), where C = \{ (a, b) : a \in A, b \in B \} and (a_1, b_1) \times (a_2, b_2) = (a_1 * a_2, b_1 \cdot b_2) for all a_1, a_2 \in A and b_1, b_2 \in B.

Two groups G=(A,*) and H=(B,\cdot) are called isomorphic if there exists a one-to-one correspondence $f$ from $A$ to $B$ such that f(a_1) \cdot f(a_2) = f(a_1*a_2) for all a_1, a_2 \in A.

The fundamental theorem of the theory of abelian groups states that any finite abelian group is isomorphic to the direct sum of some cyclic groups.

The Chinese Remainder Theorem states that Z_{mn} is isomorphic to Z_mZ_n if and only if $m$ and $n$ are coprime.

The last two statements allow us to describe all abelian groups of order $n$ up to isomorphism.

For example, if $n$ is a prime, then all groups of order $n$ are isomorphic to Z_n.

There are $2$ non-isomorphic groups of order $4$: Z_4 and Z_2Z_2.

There are $3$ non-isomorphic groups of order $27$: Z_{27}, Z_9Z_3 and Z_3Z_3Z_3.

There are $4$ non-isomorphic groups of order $36$: Z_4Z_9, Z_2Z_2Z_9, Z_4Z_3Z_3 and Z_2Z_2Z_3Z_3.