Find the number of subgroups of a finite group Definitions

You can skip this part if you already know the definitions of groups, finite groups, and subgroups.

Groups

In abstract algebra, a group is a tuple (G, &lowast;), where G is a set and &lowast; is a function G &times; G &rightarrow; G such that the following holds:


Closure: for all x, y in G, x &lowast; y is also in G (implied by the fact that &lowast; is a function G &times; G &rightarrow; G).
Associativity: for all x, y, z in G, (x &lowast; y) &lowast; z = x &lowast; (y &lowast; z).
Identity: there exists an element e in G such that for all x in G, x &lowast; e = x = e &lowast; x.
Inverse: for each x in G, there exists an element y in G such that x &lowast; y = e = y &lowast; x, where e is the identity element mentioned in the previous bullet point.


Finite groups

A finite group is a group (G, &lowast;) where G is finite, i.e. has finitely many elements.

Subgroups

A subgroup (H, &lowast;) of a group (G, &lowast;) is such that H is a subset of G (not necessarily proper subset) and (H, &lowast;) is also a group (i.e. satisfies the 4 criteria above).

Examples

Consider the dihedral group D3 (G, &lowast;) where G = {1, A, B, C, D, E} and &lowast; is defined below (a table like this is called a Cayley table):


&lowast; | 1   A   B   C   D   E
--+----------------------
1 | 1   A   B   C   D   E
A | A   B   1   D   E   C
B | B   1   A   E   C   D
C | C   E   D   1   B   A
D | D   C   E   A   1   B
E | E   D   C   B   A   1


In this group, the identity is 1. Also, A and B are inverses of each other, while 1, C, D, and E are the inverses of themselves respectively (the inverse of 1 is 1, the inverse of C is C, the inverse of D is D, and the inverse of E is E).

Now, we can verify that (H, &lowast;) where H = {1, A, B} is a subgroup of (G, &lowast;). For the closure, refer to the table below:


&lowast; | 1   A   B
--+----------
1 | 1   A   B
A | A   B   1
B | B   1   A


where all possible pairs of elements in H under &lowast; give a member in H.

The associativity does not require checking, since elements of H are elements of G.

The identity is 1. This must be the same with the group identity. Also, the identity in a group must be unique. (Can you prove this?)

For the inverse, check that the inverse of A is B, which is a member of H. The inverse of B is A, which is also a member of H. The inverse of 1 is still itself, which does not require checking.



Task

Description

Given a finite group (G, &lowast;), find the number of its subgroups.

Input

For a group (G, &lowast;), you will receive a 2D array of size n × n, where n is the number of elements in G. Assume that index 0 is the identity element. The 2D array will represent the multiplication table. For example, for the group above, you will receive the following 2D array:

[[0, 1, 2, 3, 4, 5],
[1, 2, 0, 4, 5, 3],
[2, 0, 1, 5, 3, 4],
[3, 5, 4, 0, 2, 1],
[4, 3, 5, 1, 0, 2],
[5, 4, 3, 2, 1, 0]]


For example, you can see that 3 &lowast; 1 = 5 because a[3][1] = 5, where a is the 2D array above.

Notes:


You can used 1-indexed 2D array.
The row and the column for the identity can be omitted.
You may use other formats as you see fit, but it must be consistent. (i.e. you may want the last index to be identity instead, etc.)


Output

A positive number representing the number of subgroups in the group.

For example, for the group above, (H, &lowast;) is a subgroup of (G, &lowast;) whenever H =


{1}
{1, A, B}
{1, C}
{1, D}
{1, E}
{1, A, B, C, D, E}


Therefore, there are 6 subgroups, and your output for this example should be 6.



Hints

You can read the articles that I linked to. Those articles contain theorems about groups and subgroups that might be useful to you.



Scoring

This is code-golf. Answer with lowest byte-count wins.
Mathematica, 62 48 bytes

Count[Subsets@First@#,x_/;Union@@#[[x,x]]==x]-1&amp;


Pure function expecting a 1-indexed 2D array. Counts the number of Subsets of the First row of the input array that are  closed under the group operation. Since this will include the empty set, we subtract 1. Note that a nonempty subset of a finite group that is closed under the group operation is in fact a subgroup, (and vice versa, by definition).

Strictly speaking I don't check that the subset x is closed under the group operation, I restrict the multiplication table to the subset x and check that it contains precisely the elements of x. Clearly this implies that x is closed with respect to the group operation. Conversely, any subgroup x will contain 1 and thus x will be a subset of the elements appearing in the restricted multiplication table, and since x is closed under the group operation, it must equal x.