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 <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

int N, A[6666], D[2222][2222], R[2222], M;

int main()
{
	scanf ("%d", &N);
	for (int i = 0; i < N * 3; i++) scanf ("%d", &A[i]);
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++) D[i][j] = -1e9;
		R[i] = -1e9;
	}
	M = -1e9;

	D[A[0]][A[1]] = D[A[1]][A[0]] = 0;
	R[A[0]] = R[A[1]] = M = 0;

	int base = 0;
	for (int i = 2; i + 3 < N * 3; i += 3){
		sort(A + i, A + i + 3);

		if (A[i] == A[i + 2]){ base++; continue; }
		
		struct inst{ int x, y, c; };
		vector<inst> upd;

		int w = -1, v = -1, u = -1;
		if (A[i] == A[i + 1]) w = A[i], v = A[i + 2];
		if (A[i + 1] == A[i + 2]) w = A[i + 2], v = A[i];

		if (w != -1){
			for (int p = 1; p <= N; p++){
				upd.push_back({ p, v, D[w][p] + 1 });
				upd.push_back({ p, v, R[p] });
			}
			upd.push_back({ w, w, D[v][v] + 1 });
			upd.push_back({ w, w, M });
			upd.push_back({ w, v, D[w][w] + 1 });
			upd.push_back({ w, v, M });
		}
		else{
			for (int k = 0; k < 3; k++){
				if (k == 0) w = A[i + 1], v = A[i + 2];
				if (k == 1) w = A[i], v = A[i + 2];
				if (k == 2) w = A[i], v = A[i + 1];
				u = A[i + k];

				for (int p = 1; p <= N; p++) upd.push_back({p, u, R[p]});
				upd.push_back({ w, v, D[u][u] + 1 });
				upd.push_back({ w, v, M });
			}
		}

		for (auto& t : upd){
			int x = t.x, y = t.y;
			D[x][y] = max(D[x][y], t.c);
			R[x] = max(R[x], t.c);
			M = max(M, t.c);
			swap(x, y);
			D[x][y] = max(D[x][y], t.c);
			R[x] = max(R[x], t.c);
		}
	}

	int ans = max(M, D[A[3 * N - 1]][A[3 * N - 1]] + 1) + base;
	printf ("%d\n", ans);
	return 0;
}