Setting

You are given \(n\) colorful cubes, each having a distinct weight. Cubes are not monochromatic; indeed, every face of a cube is colored with a color. Your job is to build the tallest possible tower of cubes subject to two restrictions:

  1. We never put a heavier cube on a lighter one.
  2. The bottom face of every cube (except the bottom one, of course) must have the same color as the top face of the cube below it.

Input

The input may contain several test cases separated by a blank line. The first line of each test case contains an integer \(n\) (\(1 \leq n \leq 500\)) indicating the number of cubes you are given. The \(i\)th of the next \(n\) lines contains the description of the \(i\)th cube. A cube is described by giving the colors of its faces in the following order: front, back, left, right, top, and bottom face. For your convenience (and because we care) colors are identified by integers in the range 1 to 100 (thus, more colors than most computer scientists can distinguish). You may assume that cubes are given in increasing order of their weights; that is, cube 1 is the lightest and cube \(n\) is the heaviest.

The input terminates with \(n=0\).

Output

For each test case, print the number of cubes in the tallest possible tower on a separate line.

Sample Input

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

Sample Output

2
8

This is based on challenge 10051 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

Upload Solution

Please log in to submit your solution.

Statistics

Difficulty (2 votes)
Average test runtime 0.25
Points (changes over time) 10
Tried by 3 users
Solved by 3 users

Global ranking

# Name Runtime Points worth
1 Pascal 0.14 15
2 贝尔恩德 0.22 10
3 Mac 0.38 6