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>
#define ll long long
#define reg register
#define mp make_pair
#define ri register int
using namespace std;
const int mxn=2e5+5;
int a[mxn],n;
int dp[2222][2222];
int base=1e8,mx=1e8,rmx[2222];
inline void cmax(int&a,int b){if(a<b)a=b;}
vector<tuple<int,int,int> >upd;
inline void Upd(int i,int j,int k){
	upd.emplace_back(i,j,k);
	swap(i,j);
	upd.emplace_back(i,j,k);
}
inline void solve(){
	cin>>n;
	for(int i=0;i<3*n;++i)cin>>a[i];
	dp[a[0]][a[1]]=rmx[a[0]]=rmx[a[1]]=base;
	for(int i=2;i<3*n;i+=3){
		if(a[i]==a[i+1] and a[i]==a[i+2]){
			--base;
			continue;
		}
		for(int _=0;_<3;++_){
			swap(a[i],a[i+1]),swap(a[i+1],a[i+2]);
			Upd(a[i],a[i+1],max(mx,dp[a[i+2]][a[i+2]]+1));
			for(int j=1;j<=n;++j){
				if(a[i+1]==a[i+2])Upd(j,a[i],dp[j][a[i+1]]+1);
				Upd(j,a[i],rmx[j]);
			}
		}
		for(int i=0;i<upd.size();++i){
			int e,f,g;
			tie(e,f,g)=upd[i];
			cmax(dp[e][f],g),cmax(rmx[e],g),cmax(mx,g);
		}
		upd.clear();
	}
	cout<<mx-base<<'\n';
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T=1;//cin>>T;
	for(;T--;)solve();
}