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()))
I=2*N
D=[[-I]*(N+1)for _ in range(N+1)]
M=0
r=[-I]*(N+1)
def c(i,j,k):
    D[i][j]=max(k,D[i][j])
    D[j][i]=max(k,D[j][i])
    r[i]=max(r[i],D[i][j])
    r[j]=max(r[j],D[i][j])
    global M
    M=max(M,k)
a=0
D[A[0]][A[1]]=0
D[A[1]][A[0]]=0
r[A[0]]=0
r[A[1]]=0
for i in range(N-1):
    n=A[3*i+2:3*i+5]
    C=[]
    if len(set(n))==1:
        a+=1
        continue
    if len(set(n))==2:
        for j in range(3):
            if n.count(n[j])==2:
                X=n[j]
            else:
                Y=n[j]
        for j in range(1,N+1):
            C.append((j,Y,D[X][j]+1))
    X,Y,Z =n
    C.append((X,Y,D[Z][Z]+1))
    C.append((Y,Z,D[X][X]+1))
    C.append((X,Z,D[Y][Y]+1))
    C.append((X,Y,M))
    C.append((X,Z,M))
    C.append((Y,Z,M))
    for j in range(1,N+1):
        for k in range(3):
            C.append((j,n[k],r[j]))
    for j,k,l in C:
        c(j,k,l)
M=max(M,D[A[-1]][A[-1]]+1)
print(a+M)