#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_range(i, s, e) for (int i = (s); i < (int)(e); i++)
#define rep_rev(i, s, e) for (int i = (s)-1; i >= (int)(e); i--)
#define sort_vec(v) sort((v).begin(),(v).end())
typedef int64_t lint;
// lint mod = 998244353;
// lint mod = 1000000007;
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

int app() {
  int n;
  cin>>n;

  int n3=n*3;
  vector<int> a(n3);
  rep(i,n3){
    cin>>a[i];
    a[i]--;
  }

  vector<vector<int>> dp(n,vector<int>(n,-2e9));
  vector<int> maxi(n,-2e9),maxj(n,-2e9);
  int maxall=-2e9;

  vector<pair<pair<int,int>,int>> todo;
  auto set=[&](int i,int j,int v){ todo.emplace_back(make_pair(i,j),v); };
  auto get=[&](int i,int j)->int{ return (i<=j)?dp[i][j]:dp[j][i]; };
  auto upgrade=[&](){
    for(auto u:todo){
      int i=u.first.first;
      int j=u.first.second;
      int v=u.second;
      if(i<=j) chmax(dp[i][j],v);
      else chmax(dp[j][i],v);
      chmax(maxi[i],v);
      chmax(maxi[j],v);
      chmax(maxall,v);
    }
    todo.clear();
  };

  set(a[0],a[1],0);
  upgrade();

  int common=0;
  rep(t,n-1){
    int b=2+t*3;
    if(a[b]==a[b+1]&&a[b]==a[b+2]){
      common++;
      continue;
    }
    rep(s,3){
      int c=a[b+s];
      int o1=a[b+(s+1)%3];
      int o2=a[b+(s+2)%3];

      if(o1==o2){
        rep(j,n){
          set(c,j,get(o1,j)+1);
        }
      }
      rep(j,n){
        set(c,j,maxi[j]);
      }

      set(o1,o2,get(c,c)+1);
      set(o1,o2,maxall);
    }

    upgrade();
  }

  int ans=maxall;
  int c=a[n3-1];
  chmax(ans,dp[c][c]+1);

  return ans+common;
}

int main(){cout<<app()<<endl;return 0;}

### Prompt

Generate a cpp solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep_range(i, s, e) for (int i = (s); i < (int)(e); i++)
#define rep_rev(i, s, e) for (int i = (s)-1; i >= (int)(e); i--)
#define sort_vec(v) sort((v).begin(),(v).end())
typedef int64_t lint;
// lint mod = 998244353;
// lint mod = 1000000007;
template< typename T1, typename T2 >
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 >
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

int app() {
  int n;
  cin>>n;

  int n3=n*3;
  vector<int> a(n3);
  rep(i,n3){
    cin>>a[i];
    a[i]--;
  }

  vector<vector<int>> dp(n,vector<int>(n,-2e9));
  vector<int> maxi(n,-2e9),maxj(n,-2e9);
  int maxall=-2e9;

  vector<pair<pair<int,int>,int>> todo;
  auto set=[&](int i,int j,int v){ todo.emplace_back(make_pair(i,j),v); };
  auto get=[&](int i,int j)->int{ return (i<=j)?dp[i][j]:dp[j][i]; };
  auto upgrade=[&](){
    for(auto u:todo){
      int i=u.first.first;
      int j=u.first.second;
      int v=u.second;
      if(i<=j) chmax(dp[i][j],v);
      else chmax(dp[j][i],v);
      chmax(maxi[i],v);
      chmax(maxi[j],v);
      chmax(maxall,v);
    }
    todo.clear();
  };

  set(a[0],a[1],0);
  upgrade();

  int common=0;
  rep(t,n-1){
    int b=2+t*3;
    if(a[b]==a[b+1]&&a[b]==a[b+2]){
      common++;
      continue;
    }
    rep(s,3){
      int c=a[b+s];
      int o1=a[b+(s+1)%3];
      int o2=a[b+(s+2)%3];

      if(o1==o2){
        rep(j,n){
          set(c,j,get(o1,j)+1);
        }
      }
      rep(j,n){
        set(c,j,maxi[j]);
      }

      set(o1,o2,get(c,c)+1);
      set(o1,o2,maxall);
    }

    upgrade();
  }

  int ans=maxall;
  int c=a[n3-1];
  chmax(ans,dp[c][c]+1);

  return ans+common;
}

int main(){cout<<app()<<endl;return 0;}

```