Problem: We have 3N cards arranged in a row from left to right, where each card has an integer between 1 and N (inclusive) written on it. The integer written on the i-th card from the left is A_i.

You will do the following operation N-1 times:

* Rearrange the five leftmost cards in any order you like, then remove the three leftmost cards. If the integers written on those three cards are all equal, you gain 1 point.



After these N-1 operations, if the integers written on the remaining three cards are all equal, you will gain 1 additional point.

Find the maximum number of points you can gain.

Constraints

* 1 \leq N \leq 2000
* 1 \leq A_i \leq N

Input

Input is given from Standard Input in the following format:


N
A_1 A_2 \cdots A_{3N}


Output

Print the maximum number of points you can gain.

Examples

Input

2
1 2 1 2 2 1


Output

2


Input

3
1 1 2 2 3 3 3 2 1


Output

1


Input

3
1 1 2 2 2 3 3 3 1


Output

3

Solution (in PYTHON3):

Solution:
N = int(input())
A = list(map(int,input().split()))
INF = 2*N
DP = [[-INF]*(N+1) for _ in range(N+1)]
M = 0
rowM = [-INF]*(N+1)

def chmax(i,j,k):
    DP[i][j] = max(k,DP[i][j])
    DP[j][i] = max(k,DP[j][i])
    rowM[i] = max(rowM[i],DP[i][j])
    rowM[j] = max(rowM[j],DP[i][j])
    global M
    M = max(M,k)

ans = 0
DP[A[0]][A[1]] = 0
DP[A[1]][A[0]] = 0
rowM[A[0]] = 0
rowM[A[1]] = 0
for i in range(N-1):
    new = A[3*i+2:3*i+5]
    change = []
    if len(set(new)) == 1:
        ans += 1
        continue
    if len(set(new)) == 2:
        for j in range(3):
            if new.count(new[j]) == 2:
                X = new[j]
            else:
                Y = new[j]
        for j in range(1,N+1):
            change.append((j,Y,DP[X][j]+1))
    X,Y,Z = new
    change.append((X,Y,DP[Z][Z]+1))
    change.append((Y,Z,DP[X][X]+1))
    change.append((X,Z,DP[Y][Y]+1))
    change.append((X,Y,M))
    change.append((X,Z,M))
    change.append((Y,Z,M))
    for j in range(1,N+1):
        for k in range(3):
            change.append((j,new[k],rowM[j]))
    for j,k,l in change:
        chmax(j,k,l)
M = max(M,DP[A[-1]][A[-1]]+1)
print(ans+M)