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()))
N = len(A) // 3
A = A[:3*N]
#print(N, A)
A.append(0)
A.append(0)

ans = 0
def ind(a, b):
  t = sorted((a, b))
  return t[0] * (N+1) + t[1]
def inv(i):
  b = i % (N+1)
  a = i // (N + 1)
  return a, b

dp = [-1] * (N+1)**2
dp[ind(A[0],A[1])] = 0
current_max = 0
dp1 = [-1] * (N+1)
dp1[A[0]] = 0
dp1[A[1]] = 0

ans = 0
for i in range(0, N):
  a = A[2+3*i] 
  b = A[2+3*i+1]
  c = A[2+3*i+2]
  #print(a,b,c)
  if a == b == c:
    ans+=1
    continue
  dp_new = {}
  for x, y, z in [(a, b, c), (b, c, a), (c, a, b)]:
    # choose 1 (x), leave y, z
    i = ind(y, z)
    if i not in dp_new:
      dp_new[i] = 0
    dp_new[i] = max(dp_new[i], current_max)
    if dp[ind(x, x)] >= 0:
      dp_new[i] = max(dp_new[i], dp[ind(x, x)] + 1)
    
    # choose 2 (x, y), leave t, z
    for t in range(1, N+1):
      i = ind(t,z)
      # Not making three
      if dp1[t] >= 0:
        if i not in dp_new:
          dp_new[i]=0
        dp_new[i] = max(dp_new[i], dp1[t])
      # Making three (x==y)
      if x == y and dp[ind(t, x)] >= 0:
        if i not in dp_new:
          dp_new[i] = 0
        dp_new[i] = max(dp_new[i], dp[ind(t, x)] + 1)
        
  #print(a,b,c)
  #print({inv(i):v for i, v in dp_new.items() })
  for i, s in dp_new.items():
    dp[i] = max(dp[i], s)
    ta, tb = inv(i)
    dp1[ta] = max(dp1[ta], s)
    dp1[tb] = max(dp1[tb], s)
    current_max = max(current_max, s)

#print(doubles)
print(ans + max(dp1))