Under construction

Still being built. Things may change

Colored Cubes

Time limit2sMemory limit512 MB

Summary
Count how many distinct cube colorings appear in each test case, where two cubes match if some rotation makes all six face colors agree.
Level

Medium4 of 10

Topics
Implementation, Hash map, Geometry
Solved
No attempts yet

Problem

Children love playing with small cubes. They spend hours building 'houses', 'buildings', and so on. Tomaz's little brother just got a set of colored blocks for his birthday. Each face of each cube has one color.

Tomaz is a very analytical child, so he decided to find out how many different "types" of cubes his little brother received. Can you help him? Two cubes are of the same type if one of them can be rotated so that the colors on the corresponding faces of the two cubes are equal.

Input

The input contains several test cases. The first line of each test case contains an integer NN, the number of cubes in the set (1≤N≤10001 \le N \le 1000). The next 3N3N lines describe the cubes of the set. Colors are identified by the integers 0 to 9.

Each cube is given in three lines that show the colors of the six faces of the "unfolded" cube, in the format below.

1
2 4 5 6
3

In this example the faces of the cube have colors 1 to 6. The face with color 1 is opposite the face with color 3. The face with color 2 is adjacent to the faces with colors 1, 3, 4, and 6, and it is opposite the face with color 5.

The end of input is marked by N=0N = 0.

Output

For each test case, print one line with a single integer: the number of cube types in the given set.

Examples1

  1. Example 1

    Input
    3
0
0 7 2 3
1
0
1 2 3 7
0
3
0 0 2 1
7
2
1
1 1 1 1
1
2
2 2 2 2
2
0
    Expected output
    2
2