Unique Dice

Interview

Time limit7sMemory limit1024 MB

Summary

Given n dice with six face values each, find the largest group of dice that match after some rotation.

Level: Medium4 of 10
Topics: Hash map, Implementation
Solved: No attempts yet

Problem

You are about to leave home for your weekly game of Pumpkins and Flagons (P&F) when a text comes in asking you to bring a large collection of identical P&F dice. They have asked the right person, for you have a very large collection of P&F dice, which is currently unsorted.

Each die is an ordinary cube with a number on each of its six faces. The numbers are in the range 1 to 6, but they do not need to be distinct. For example, $\{ 1, 2, 3, 4, 5, 6 \}$ , $\{ 1, 1, 1, 1, 1, 1 \}$ , and $\{ 2, 2, 2, 4, 4, 5 \}$ are all valid sets of numbers for the six faces. Find the size of the largest set of identical dice you can create from your collection. Two dice are identical if you can rotate one of them so that the top, bottom, and all four side faces show the same numbers as the other.

Figure 1: The six faces of a die.

Input

The first line contains an integer $n$ ( $1 \leq n \leq 500\,000$ ), the number of dice in your collection. The next $n$ lines each contain six integers from 1 to 6, separated by spaces. They give the numbers on the top, bottom, front, back, left, and right faces, in that order (see Figure 1).

Output

Print a single integer, the size of the largest set of identical dice that can be made from the collection.

Examples3

Example 1
Input
```
2
1 6 2 5 4 3
1 6 3 4 2 5
```
Expected output
```
2
```
Example 2
Input
```
2
1 6 2 5 3 4
1 6 3 4 2 5
```
Expected output
```
1
```

Example 3

Input

5
1 1 2 2 2 2
1 2 1 2 2 2
1 2 2 1 2 2
1 2 2 2 1 2
1 2 2 2 2 1

Expected output