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;
using ll = long long;
using ull = unsigned long long;
constexpr int inf = 1<<30;
constexpr int mo = 1e9+7;
constexpr ll infl = 1ll<<60;

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    int n;
    cin>>n;
    vector<int> a(3*n);
    for(auto & b : a) cin>>b,b--;
    vector<vector<int>> dp(n,vector<int>(n,-(1<<20)));
    vector<int> ma(n,-(1<<20));
    dp[a[0]][a[1]] = 0;
    ma[a[0]] = ma[a[1]] = 0;
    int ret = 0;
    for(int i=2;i+2<3*n;i+=3){
        sort(a.begin()+i,a.begin()+i+3);
        if(a[i] == a[i+2]){
            ret++;
            continue;
        }
        
        vector<tuple<int,int,int>> co;
        if(a[i] == a[i+1]){
            for(int x=0;x<n;++x){
               co.emplace_back(x,a[i+2],max(dp[a[i]][x],dp[x][a[i]])+1); 
            }
        }
        if(a[i+1] == a[i+2]){
            for(int x=0;x<n;++x){
                co.emplace_back(x,a[i],max(dp[a[i+1]][x],dp[x][a[i+1]])+1);
            }
        }
                
        for(int j=i;j<i+3;++j){
            for(int x=0;x<n;++x)co.emplace_back(x,a[j],ma[x]);
        }
        
        co.emplace_back(a[i],a[i+1],dp[a[i+2]][a[i+2]]+1);
        co.emplace_back(a[i+1],a[i+2],dp[a[i]][a[i]]+1);
        co.emplace_back(a[i],a[i+2],dp[a[i+1]][a[i+1]]+1);

        
        int tmp = -1;
        for(int x=0;x<n;++x) tmp = max(tmp,ma[x]);
        co.emplace_back(a[i],a[i+1],tmp);
        co.emplace_back(a[i+1],a[i+2],tmp);
        co.emplace_back(a[i],a[i+2],tmp);
        
        for(auto  cur : co){
            int a,b,c;
            tie(a,b,c) = cur;
            dp[a][b] = max(dp[a][b],c);
            ma[a] = max(ma[a],c);
            ma[b] = max(ma[b],c);
        }
    }
    
    int sma = 0;
    for(int i=0;i<n;++i) sma = max(sma,ma[i]);
    sma = max(sma,dp[a[3*n-1]][a[3*n-1]] + 1);
    cout << ret+sma << endl;
    return 0;
}