Longest Possible Milital Chain

Time Limit: 3 Seconds    Memory Limit: 131072 KB

You are invited to the Milital Contest to create the longest Milital chain. Milital is a metal shape that has two clips on opposite sides (c₁ and c₂ in the picture below). They are in different weights and Militals with different weights have different shapes. There are n different shapes and 10⁵ different clips in this contest. Clips in one Milital may not be similar. Two clips can be attached to each other, if they are of the same kind.

You are given n boxes of Militals in each there are exactly 3 Militals of the same weight but may be different in their clips and It is guaranteed that there is no pair of boxes with same weights. You must create the longest possible chain of given Militals and hang it to the counter machine. This machine lifts up your chain and counts number of its Militals. Here are contest rules:

· You cannot use more than one Milital of the same weight (in other words you can use at most one Milital from each box).

· You are not allowed to use lighter Militals under heavier ones.

Write a program to compute number of Militals in the maximum possible chain.

Input

The first line of each test case, contains integer n, with 1 <= n <= 10⁵, denoting number of boxes. Boxes are numbered from 1 to n in order of increasing weight. Militals in boxes with lower number are lighter than those in boxes with higher number.

Following n lines, each contains 3 pairs of integers denoting type of clips for Militals in each box. Types are numbered from 1 to 10⁵. All integers are separated by a single space.

The last line of input is single zero and should not be processed.

Output

There is a single line of output for each test case with maximum possible number of Militals in a chain.

Sample Input

3
1 2 2 2 1 2
3 3 3 3 3 3
3 2 1 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

Submit