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<cstdio>
#include<algorithm>
#include<stack>
#define st first
#define nd second

using namespace std;
struct O{
		int st;
		int nd;
		int val;
};
const int N = 2e3 + 10;

int dp[N][N],   a[3 * N], fr[N] , ba[N];

int main()
{
	int n;
	scanf("%d", &n);
	for(int i = 1; i <= 3 * n; i++) {
		scanf("%d", &a[i]);
	}
	dp[a[1]][a[2]] = dp[a[2]][a[1]] = ba[a[2]] = ba[a[1]] = fr[a[2]] = fr[a[1]] =1;
	int col = 0, ma = 1;
	for(int i = 3; i < 3 *  n; i += 3){
		if(a[i] == a[i + 1] && a[i] == a[i + 2]) {
			col ++;
			continue;
		}
		sort(a + i, a + i + 3);
		stack<O> stx;
		if(a[i + 1] == a[i + 2]){
			swap(a[i], a[i + 2]);	
		}	    
		if(a[i] == a[i + 1]){
			for(int j = 1; j <= n; j++){
				if(ba[j] != 0) stx.push({a[i + 2], j, max(dp[a[i]][j] + 1, ba[j])});
				if(fr[j] != 0) stx.push({j, a[i + 2], max(dp[j][a[i]] + 1, fr[j])});
			}
			stx.push({a[i], a[i], max(dp[a[i + 2]][a[i + 2]] + 1, ma)});			
		}
		else{
			int x = max(ma, dp[a[i]][a[i]] + 1), y = max(ma, dp[a[i + 1]][a[ i +1]] + 1), z = max(ma, dp[a[i + 2]][a[i+2]] + 1);
			stx.push({a[i + 1], a[i + 2], x}), stx.push({a[i], a[i + 2], y}), stx.push({a[i], a[i + 1], z});
			stx.push({a[i + 2], a[i + 1], x}), stx.push({a[i + 2], a[i], y}), stx.push({a[i + 1], a[i], z});
			for(int j = 1; j <= n; j++){
				for(int k = 0; k < 3; k++){
					if(fr[j] !=  0) stx.push({j, a[i + k], fr[j]});
					if(ba[j] != 0)  stx.push({a[i + k], j, ba[j]});
				}
			}
		}
		while(!stx.empty()){
			int x = stx.top().st, y = stx.top().nd, z= stx.top().val;
			stx.pop();
			dp[x][y] = max(dp[x][y], z);
			fr[x] = max(fr[x], z);
			ba[y] = max(ba[y],  z);
			ma = max(ma, z);
		}	
	}
	printf("%d", col +  max(ma, dp[a[3 *n]][a[3 * n]] + 1) - 1);
}