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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
const int MAXN = 6005;
const int INF = 1e5;

int N;
int A[MAXN];

int ans = 0;
int base = 0;
int nxt[MAXN];
int dp[MAXN][MAXN];

int Cost(int a, int b, int c) {
  return A[a] == A[b] && A[b] == A[c];
}

void Transition(int i, int j, int cur) {
  if (cur > 3 * N) return;
  if (cur == 3 * N) {
    ans = max(ans, dp[i][j] + Cost(i, j, cur));
    return;
  }
  dp[cur + 0][cur + 1] = max(dp[cur + 0][cur + 1], dp[i][j] + Cost(i, j, cur + 2));
  dp[cur + 0][cur + 2] = max(dp[cur + 0][cur + 2], dp[i][j] + Cost(i, j, cur + 1));
  dp[cur + 1][cur + 2] = max(dp[cur + 1][cur + 2], dp[i][j] + Cost(i, j, cur + 0));

  dp[i][cur + 0] = max(dp[i][cur + 0], dp[i][j] + Cost(j, cur + 1, cur + 2));
  dp[i][cur + 1] = max(dp[i][cur + 1], dp[i][j] + Cost(j, cur + 0, cur + 2));
  dp[i][cur + 2] = max(dp[i][cur + 2], dp[i][j] + Cost(j, cur + 0, cur + 1));

  dp[j][cur + 0] = max(dp[j][cur + 0], dp[i][j] + Cost(i, cur + 1, cur + 2));
  dp[j][cur + 1] = max(dp[j][cur + 1], dp[i][j] + Cost(i, cur + 0, cur + 2));
  dp[j][cur + 2] = max(dp[j][cur + 2], dp[i][j] + Cost(i, cur + 0, cur + 1));
  dp[i][j] = max( dp[i][j], dp[i][j] + Cost(cur+0, cur + 1, cur + 2));

}

int main() {

  cin >> N;
  for (int i = 1; i <= 3 * N; i++)
    cin >> A[i];


  while (true) {
    bool change = false;
    for (int i = 3; i + 2 <= 3 * N; i += 3) {
      if (A[i] == A[i + 1] && A[i + 1] == A[i + 2]) {
        base += 1;
        for (int j = i + 3; j <= 3 * N; j++) {
          A[j - 3] = A[j];
        }
        N -= 1;
        change = true;
        break;
      }
    }
    if (!change) {
      break;
    }
  }

  vector<int> last(3 * N + 1, 3 * N + 1);
  for (int i = 3 * N; i > 0; i--) {
    nxt[i] = last[A[i]];
    last[A[i]] = i;
  }
  for (int i = 0; i < MAXN; i++) {
    for (int j = 0; j < MAXN; j++) {
      dp[i][j] = -INF;
    }
  }
  dp[1][2] = 0;
  for (int i = 1; i <= 3 * N; i++) {
    for (int j = i + 1; j <= 3 * N; j++) {
      Transition(i, j, (j + 3) / 3 * 3);
            Transition(i, j, (j + 3) / 3 * 3);

      // Find next occurrence of A[i]
      if ( ((j + 3) / 3 * 3) <= (nxt[i] / 3 * 3) )
        Transition(i, j, nxt[i] / 3 * 3);

      // Find next occurrence of A[j]
      if ( ((j + 3) / 3 * 3) <= (nxt[j] / 3 * 3) )
        Transition(i, j, nxt[j] / 3 * 3);

    }
  }

  cout << ans + base << "\n";
  return 0;
}