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;

#define ll long long
#define mp make_pair
#define pb push_back

#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define rep(i, n) for (int i = 0; i < (int)(n); ++ i)

int n, a[6005], dp[2005][2005], rmx[2005], mx;
int todo[100005][3], tsz;

void add_todo(int x, int y, int v) { todo[tsz][0] = x; todo[tsz][1] = y; todo[tsz ++][2] = v; }
void upd(int x, int y, int v) { rep(_, 2) { dp[x][y] = max(dp[x][y], v); rmx[x] = max(rmx[x], v); mx = max(mx, v); swap(x, y); } }
void fix() { rep(i, tsz) upd(todo[i][0], todo[i][1], todo[i][2]); tsz = 0; }

int main() {
	scanf("%d", &n);
	rep(i, n * 3) scanf("%d", &a[i]), -- a[i];
	memset(rmx, -0x3f, sizeof(rmx));
	memset(dp, -0x3f, sizeof(dp));
	mx = -0x3f3f3f3f;
	upd(a[0], a[1], 0);
	int extra = 0;
	rep(i, n - 1) {
		int x[3] = { a[i * 3 + 2], a[i * 3 + 3], a[i * 3 + 4] };
		if (x[0] == x[1] && x[1] == x[2]) { ++ extra; continue; }
		rep(_, 3) {
			add_todo(x[0], x[1], max(mx, dp[x[2]][x[2]] + 1));
			rep(j, n) {
				if (x[0] == x[1]) add_todo(j, x[2], dp[j][x[0]] + 1);
				add_todo(j, x[2], rmx[j]);
			}
			swap(x[0], x[1]); swap(x[1], x[2]);
		}
		fix();
	}
	int ans = mx;
	ans = max(ans, dp[a[n * 3 - 1]][a[n * 3 - 1]] + 1);
	printf("%d\n", ans + extra);
	return 0;
}