Generating the Subgroups of a Finite Group

Time Limit: 1 Second    Memory Limit: 32768 KB

In the study of abstract algebra, a mathematical structure you are introduced to early in the subject is the GROUP. Technically, a group is a coordinate pair consisting of a set and a binary operator, although the set can also be referred to as a group under the binary operator. The binary operator of the group must have the following properties: 1.) it must be closed over the set of the group; 2.) it must be associative over the set of the group; 3.) the set must have an identity element under the binary operator; and, 4.) each element must have an inverse under the binary operator. For example, the set of integers is a group under addition, but is not a group under multiplication.

Each group may, in turn, have subgroups, which consists as a subset of the group and the same binary operator. The subgroup, of course, is a group by itself. From the above example, the set of even integers is a subgroup of the group of integers under addition.

The study of groups underlies many self-contained deterministic mathematical structures, and the study of finite groups is a staple of abstract algebra. An example of a finite group is the remainder set of modulo 9 (that is, {0, 1, 2, 3, 4, 5, 6, 7, 8}) under addition modulo 9. It must be noted that each subgroup subdivides the parent group into exclusive equal-sized sets called equivalence classes, or cosets. For example, the set of even integers generates the equivalence classes of the set of even numbers and the set of odd numbers. For another example, the group of the remainder set of modulo 9 has a subgroup {0, 3, 6} which generates the equivalence classes {0, 3, 6}, {1, 4, 7} and {2, 5, 8}.

You are asked to generate all of the subgroups of a given finite group.

Input

In the input, the first line will contain the number of groups you will analyze, which will be a number from 1 to 5. This will be followed by blocks containing the groups themselves.

Each block for one group will start with a line with a number n from 1 to 24. This will be the size (number of elements) of (the set of) the group. The elements of (the set of) the group will be {0, 1, ..., n-1}. This will be followed by the group table, which is composed n lines, each of which should be a permutation of 0, 1, ... , n-1, the numbers separated by commas. The group table will determine the results of the binary operation of the group. To elaborate, if ~ denotes the binary operator of the group, the fifth number on the third line of a group table indicates the result of 2~4. In general, the result of m~n is the (n+1)th number on the (m+1)th line of the group table.

Each group indicated thus can be assumed to follow the description of a group, and its implied binary operator will be closed over the set, be associative, have an identity element, and each element will have an inverse element.

Output

Output must contain the proper subgroups of each of the groups indicated in "groups.in". Proper subgroups are proper subsets of the set of a group.

The elements of each subgroup must be sorted in increasing order. For each group, the subgroups must be sorted by increasing size, and for subgroups of the same size, the subgroups must be sorted by increasing elements: {2, 4, 7, 8} will come before {2, 4, 7, 10} and {2, 5, 6, 7}.

After listing the subgroups of each group, show a line starting with 3 asterisks and followed by a space and a number indicating the number of subgroups of that group.

Sample Input

2
9
0,1,2,3,4,5,6,7,8
1,2,3,4,5,6,7,8,0
2,3,4,5,6,7,8,0,1
3,4,5,6,7,8,0,1,2
4,5,6,7,8,0,1,2,3
5,6,7,8,0,1,2,3,4
6,7,8,0,1,2,3,4,5
7,8,0,1,2,3,4,5,6
8,0,1,2,3,4,5,6,7
4
2,3,0,1
3,2,1,0
0,1,2,3
1,0,3,2

Sample Output

0
0, 3, 6
*** 2
2
0, 2
1, 2
2, 3
*** 4

Submit

Source: Asia 2003, Manila (Philippine)