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;
const int MAXN = 6005;
const int INF = 1e5;
int A[MAXN], nxt[MAXN], dp[MAXN][MAXN], ans = 0, base = 0, N;
inline int Cost(int a, int b, int c) { return A[a] == A[b] && A[b] == A[c]; }
void chmax(int &x, int val) { x = max(x, val); }
inline void Transition(int i, int j, int cur) {
  if (cur > 3 * N) return;
  if (cur == 3 * N)
    return void(chmax(ans, dp[i][j] + Cost(i, j, cur)));
  for (int u = 1; u <= 3; ++u)
    for (int v = u + 1; v <= 3; ++v)
      chmax(dp[cur + u - 1][cur + v - 1], dp[i][j] + Cost(i, j, cur + (u ^ v) - 1));
  for (int c : {i, j}) {
    chmax(dp[c][cur + 0], dp[i][j] + Cost(i ^ j ^ c, cur + 1, cur + 2));
    chmax(dp[c][cur + 1], dp[i][j] + Cost(i ^ j ^ c, cur + 0, cur + 2));
    chmax(dp[c][cur + 2], dp[i][j] + Cost(i ^ j ^ c, cur + 0, cur + 1));
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> N;
  for (int i = 1; i <= 3 * N; i++) {
    cin >> A[i];
    if (i % 3 == 2 && i >= 5 && Cost(i, i - 1, i - 2)) i -= 3, --N, ++base;
  }
  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);
      if (j / 3 * 3 < nxt[i] / 3 * 3)
        Transition(i, j, nxt[i] / 3 * 3);
      if (j / 3 * 3 < nxt[j] / 3 * 3)
        Transition(i, j, nxt[j] / 3 * 3);
    }
  }
  cout << ans + base << "\n";
  return 0;
}